再谈KMP算法

KMP算法是串匹配中的经典算法，算法复杂度为$O(m+n)$。我们熟悉的str函数一般是用简单匹配算法实现的，最坏情况下的复杂度是$O(m*n)$。KMP算法的特点是，每当匹配时出现字符不同时，不需要回溯主串指针，整个匹配过程中只需要对主串从头到尾扫描一遍就可以了。

KMP算法的思想很简单。假设主串为S1S2...Sn，模式串为P1P2...Pm。如果P1P2...Pi （1 <= i <= n）和主串中的某一子串SjSj+1...Sj+i-1匹配，而Pi+1 <> Sj+i，如果我们发现P1P2...Pk = Pi-k+1...Pi（1 <= k < i），那么显然我们可以从Pk+1和Sj+i开始继续匹配了。简单吧。

现在问题的关键就时对于i (1 <= i <= m)怎么求出最大的k使得P1P2...Pk = Pi-k+1...Pi。我们可以用一个数组：

int next[m]; 预先计算出值。

计算next数组最简单的方法就是穷举法，算法的复杂度为$O(m*m)$，整个算法的复杂度为$O(m*m+n)$。

不过还有复杂度为$O(m)$的算法，思想如下：假设P1P2...Pk = Pi-k+1...Pi，那么next[i] = k + 1 。当我们计算next[i+1]时，如果发现Pk+1 = Pi+1, 也就是P1P2...PkPk+1 = Pi-k+1...PiPi+1，那么next[i+1] = next[i] + 1 = k + 2。 但是如果Pk+1 <> Pi+1, 则比较next[k]和Pi+1（找下一个满足P1P2...Pk' = Pi-k'+1...Pi的k'）,一直到匹配成功为止。

最后：简单匹配算法虽然最坏情况下的复杂度是$O(m*n)$，但一般情况下复杂度接近$O(m+n)$，所以现在还在大量使用。