题目
实现函数：输入一个长度为n的字符串，输出长度为n的数组，其中第i位表示从0到i的子串的最长前后缀长度。例如abaab的最长前后缀长度为2.
解决
- 暴力法
对于长度为m的子串，看长度为m-1的前缀、后缀是否相同，相同则返回，否则再看m-2，依次类推
时间复杂度为O(n)。代码略 -
更高效的方法
观察到这样一个事实：
当output[i]=len时，计算output[i+1]：
若input[i+1]==input[len]，即考察的前后缀长度加1后仍然相等，则output[i+1]=len+1
否则，若len>0，则令len=output[len-1]，再继续考察input[i+1]与input[len]；若len=0，则output[i+1]=0。原因如下图所示：
代码
public static int[] getLPS(String str) {
int[] result = new int[str.length()];
int i=1;
int len = 0;
while(i<str.length()){
if (str.charAt(i) == str.charAt(len)){
len ++;
result[i] = len;
i ++;
}
else if(len>0){
len = result[len-1]; //尝试第二长的前后缀，看是否能继续
}
else
i ++; //没有更小的候选答案了，则为0
}
return result;
}
应用：字符串匹配（KMP）
题目
实现KMP匹配算法，空串可以匹配任意字符串，失配则返回-1
代码
public static int strStr(String str, String pattern){
int m = str.length();
int n = pattern.length();
if (n==0)
return 0;
int[] lps = getLPS(str);
int i = 0;
int j = 0;
while(i<m){
if (str.charAt(i) == pattern.charAt(j)){
i ++;
j ++;
if (j==n)
return i-n;
}
else if (i>0)
j = lps[j-1];
else
i ++;
}
return -1;
}
解释
另一种方法是求next数组，具体方法为next[0]=0或-1，next的其余元素为最长前后缀长度加1.例如模式串“aaba”的next数组为{0，2，1，2}
两种方法的区别在于：
首先next（或lps）数组的计算方式不同
使用next数组进行匹配时，若在第j位失配，则令j=next[j]
而上述方法则是令j=lps[j-1]
