首先需要明白 KMP 算法是什么，可以阅读这两篇博客文章：KMP 算法 - 刘毅、字符串匹配的KMP算法 - 阮一峰 。
实现 KMP 算法的关键是 双指针 和 next 数组的生成。next[j] 表示当 j 位置的字符不匹配时，j 应该移动到哪个位置。next[j] 是 -1 时表示要完全跳过（i++;j = 0;），比如 next[0] 一定是 -1，因为第一个字符都不匹配，当然就是直接跳过了。
这里我讲一下 KMP 算法的 next 数组的生成。next 数组是通过模式串自己跟自己匹配计算出来的，假设我们的模式串，即搜索的目标是“abac”，其 next 数组的计算过程如下：
// (1) 一开始，next[0] == -1
i = 1
next = -1
['a', 'b', 'a', 'c']
['a', 'b', 'a', 'c']
j = 0
// (2.0) 当 next[i] != next[j] 时，next[i] = j
i = 1
next = -1 0
['a', 'b', 'a', 'c']
['a', 'b', 'a', 'c']
j = 0
// (2.1) j = next[j]
i = 1
next = -1 0
['a', 'b', 'a', 'c']
['a', 'b', 'a', 'c']
j = -1
// (3) i++; j++;
i = 2
next = -1 0
['a', 'b', 'a', 'c']
['a', 'b', 'a', 'c']
j = 0
// (4) 当 next[i] == next[j] 时，next[i] = next[j]
i = 2
next = -1 0 -1
['a', 'b', 'a', 'c']
['a', 'b', 'a', 'c']
j = 0
// (5) i++; j++;
i = 3
next = -1 0 -1
['a', 'b', 'a', 'c']
['a', 'b', 'a', 'c']
j = 1
// 剩下就是根据 next[i] 和 next[j] 是否相等，循环 (2.0) 或 (4) 操作
KMP 算法的时间复杂度为 O(n + m) ，空间复杂度为 O(m) ，它的 Java 的实现如下：
public final class KMP {
private KMP() {
// private
}
public static int search(String str, String target) {
int n = str.length(), m = target.length();
if (m == 0) return 0;// 这一行不能少
if (n < m) return -1;
int[] next = getNext(target);
for (int i = 0, j = 0; i < n; i++, j++) {
while (j > -1 && str.charAt(i) != target.charAt(j)) j = next[j];
if (j == m - 1) return i - j;
}
return -1;
}
static int[] getNext(String target) {
int[] next = new int[target.length()];
next[0] = -1;
for (int i = 1, j = 0; i < target.length(); i++, j++) {
if (j == -1) continue;
if (target.charAt(i) != target.charAt(j)) {
next[i] = j;
j = next[j];
} else {
next[i] = next[j];
}
}
return next;
}
}
由于
- 空间复杂度 O(m) 不够好
- 实现过程复杂，容易出错
实际应用中很少选择 KMP 算法。