題目
實現(xiàn)函數(shù)：輸入一個長度為n的字符串踩晶，輸出長度為n的數(shù)組，其中第i位表示從0到i的子串的最長前后綴長度枕磁。例如abaab的最長前后綴長度為2.
解決
- 暴力法
對于長度為m的子串渡蜻，看長度為m-1的前綴、后綴是否相同计济，相同則返回茸苇，否則再看m-2，依次類推
時間復(fù)雜度為O(n)沦寂。代碼略 -
更高效的方法
觀察到這樣一個事實：
當(dāng)output[i]=len時学密，計算output[i+1]：
若input[i+1]==input[len]，即考察的前后綴長度加1后仍然相等传藏，則output[i+1]=len+1
否則腻暮，若len>0，則令len=output[len-1]漩氨，再繼續(xù)考察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]; //嘗試第二長的前后綴款青，看是否能繼續(xù)
}
else
i ++; //沒有更小的候選答案了，則為0
}
return result;
}
應(yīng)用：字符串匹配（KMP）
題目
實現(xiàn)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數(shù)組，具體方法為next[0]=0或-1蔗坯，next的其余元素為最長前后綴長度加1.例如模式串“aaba”的next數(shù)組為{0康震，2，1宾濒，2}
兩種方法的區(qū)別在于：
首先next（或lps）數(shù)組的計算方式不同
使用next數(shù)組進行匹配時腿短，若在第j位失配，則令j=next[j]
而上述方法則是令j=lps[j-1]
