KMP算法是用来查看一个字符串是否包含另一个字符串的算法，暴力求解的时间复杂度是O(m*n)，而KMP算法的时间复杂度是O(m+n)，KMP算法的关键概念如下：
- 前缀 abcdab的前缀集合为a,ab,abc,abcda
- 后缀 abcdab的后缀集合为bcdab,cdab,dab,ab,b
- 部分匹配值 部分匹配值就是前缀和后缀最长的共有元素的长度，比如abcdab前缀和后缀最长的共有元素是ab,其长度是2
- next值 当前字符前（不含当前字符）的字符串的部分匹配值，比如abcdab最后b的next值就是abcda的部分匹配值，也就是1
- 部分匹配值数组 设一个字符串string的长度为n，则部分匹配值数组array有n个元素，且array[i]的值为字符串string.sub(0, i+1)的部分匹配值，比如abcdab的部分匹配值数组为0,0,0,0,1,2
- next数组 设一个字符串string的长度为n，则next数组array有n个元素，且array[i]的值为字符串string.sub(0, i+1)的next值，特别的， array[0]永远等于-1,array[1]永远等于0, next数组可以用部分匹配值数组右移，然后在第一个元素补上-1得到。例如abcdab的部分匹配值数组为0,0,0,0,1,2,右移后为0,0,0,0,1,补充-1后为-1,0,0,0,0,1
next数组的作用在于计算模版P匹配字符串A失配后，需要在当前位置后移多少位继续匹配。设失配字符为模版P的第i个字符，计算公式为distance = i - next(i)
实例代码如下：
public class KMP {
private static int[] getNextArray(final String pattern) {
if (pattern == null || pattern.isEmpty()) {
return null;
}
int[] next = new int[pattern.length()];
next[0] = -1;
int k = -1;
int j = 0;
while (j < (pattern.length() - 1)) {
if (k == -1 || pattern.charAt(k) == pattern.charAt(j)) {
k++;
j++;
next[j] = k;
} else {
k = next[k];
}
}
return next;
}
private static void printArray(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]);
sb.append(' ');
}
sb.append('\n');
System.out.print(sb.toString());
}
public static int kmpFind(final String src, final String pattern) {
if (src == null || pattern == null) {
return -1;
}
int lenSrc = src.length();
int lenPattern = pattern.length();
if (lenSrc < lenPattern) {
return -1;
}
int[] next = getNextArray(pattern);
if (next == null) {
return -1;
}
int result = -1;
int i = 0;
while (i < lenSrc) {
int j = 0;
while (j < lenPattern) {
if (src.charAt(i) != pattern.charAt(j)) {
break;
}
i++;
j++;
}
if (j < lenPattern) {
int move = j - next[j];
i = i - j + move;
result = -1;
} else {
result = i - lenPattern;
break;
}
}
return result;
}
public static void main(String[] argv) {
System.out.print(String.format("find %s in %s : %d\n", argv[1],
argv[0],
kmpFind(argv[0], argv[1])));
}
}
