關(guān)鍵在于實現(xiàn)最長公共前后綴table狸捕。一個字符串的最長公共前后綴舉例：比如"abcdabc"的最長公共前后綴為“abc”, "aaaa"的最長公共前后綴為“aaa”(不包括自己)。
private boolean kmp(String target, String pattern) {
int m = target.length(), n = pattern.length();
int i = 0, j = 0;
int[] prefixTable = getPrefixTable(pattern);
while (i < m && j < n) {
if (target.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = prefixTable[j-1];
}
}
return j == n;
}
private int[] getPrefixTable(String pattern) {
int n = pattern.length();
int[] prefix = new int[n];
prefix[0] = 0;
for (int i=1; i<n; i++) {
int len = prefix[i-1];
while (pattern.charAt(len) != pattern.charAt(i)) {
if (len == 0) {
len--; break;
}
len = prefix[len-1];
}
prefix[i] = len + 1;
}
return prefix;
}
