KMP算法是一种高效的字符串匹配算法。通常，在求两个字符串是否匹配是，都是枚举一个字符串的开头与另一个字符串匹配， 假如 A 串长度为 n ， B 串长度为 m ， 那么这种方法的复杂度是 O(nm)的。而KMP能在O(n)的时间内完成。
【KMP思想】
如图，假设有A,B两个字符串要求匹配，当匹配到A[i]、B[j]时，A[1..i-1]与B[1..j-1]完全匹配，但A[i]!=B[j]。通常，遇到这种情况，都是再枚举开头，重新进行匹配，但是这会浪费很多时间。仔细观察，发现B串的a部分与b部分完全相同，那么可以适当减少j的值（相当于把B串往后移动），那么匹配便可以继续进行。如下图。
显而易见，j减少的多少与A无关，只与B有关。 我们完全可以预处理出这样一个数组 next[j]， 表示当匹配到 B 数组的第 j 个字母而第 j +1个字母不能匹配了时， 新的 j 最大是多少。 next[j] 应该是所有满足 B[1..k]= B[ j- k+1... j]的k (k < j) 的最大值。
于是容易得出KMP的代码：
2
3
4
5
6
7
8
9
int j = 0;
for (int i = 1;i <= m; i++) {
while (j && b[i] != a[j + 1]) j = next[j];
if (b[i] == a[j + 1]) ++j;
if (j == n)
j = next[j];
}
}
最后的 j=next[j]是为了让程序继续做下去， 因为我们有可能找到多处匹配。
那么next数组要怎么求呢?
假设我们现在已经求得next[1]、next[2]、……next[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求next[i+1]。
如果位置i+1和位置next[i+1]处的两个字符相同（下标从零开始），则next[i+1]等于next[i]加1。- 如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造，如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。
怎么这个预处理过程跟前面的 KMP 主程序这么像呢？ 其实， KMP 的预处理本身就是一
个 B 串“自我匹配” 的过程。
2
3
4
5
6
7
8
9
int j = 0;
next[1] = 0;
for (int i = 2;i <= n; i++) {
while (j && a[j + 1] != a[i]) j = next[j];
if (a[j + 1] == a[i]) j++;
next[i] = j;
}
}
最后为什么KMP的代码会是O(n)的呢?
我们从上述程序的 j 值入手。 每一次执行 while 循环都会使 j减小（ 但不能减成负的） ， 而另外的改变 j 值的地方只有一处。 每次执行了这一处， j 都只能加 1； 因此， 整个过程中 j 最多加了 n 个 1。 于是， j 最多只有 n 次减小的机会（j 值减小的次数当然不能超过 n ， 因为 j 永远是非负整数） 。 这告诉我们， while 循环总共最多执行了 n 次。 按照摊还分析的说法， 平摊到每次 for 循环中后， 一次 for 循环的复杂度为O(n)
整个过程显然是O(n) 的。 这样的分析对于后面next数组预处理的过程同样有效， 同样可以得到预处理过程的复杂度为 O(n)。
完整代码如下： 继续阅读KMP(字符串匹配)
