KMP算法 - 深入浅出
原理在朴素算法中，移动模式串后，就会丢掉之前已匹配符号的信息。所以，很可能一个文本符号会与不同的模式符号进行多次比较。这导致了最坏时间复杂度O(nm)（n:文本长度，m: 模式长度）。

KMP算法利用之前的符号比较信息。该算法不会对已经与某个模式符号匹配的文本符号进行重复比较。所以KMP的时间复杂度是O(n)。

然而，需要对模式串进行预处理以分析它的结构。预处理阶段的时间复杂度是O(m)。因为m<=n，所以总的时间复杂度是O(n)。

基本定义

定义：设A是一个字母表，x =x0 ...xk-1,k∈ N 是一个由A中的字母构成的长度为k的字符串。

x的一个前缀是一个子串u：

u =x0 ...xb-1 whereb∈{0, ...,k}

x的一个后缀是一个子串u:

u =xk-b ... xk-1 whereb∈{0, ...,k}

如果u≠x,例如u的长度b小于k，则u分别叫做真前缀或真后缀。

x的边界串(border)是一个子串r:

r =x0 ...xb-1 and r =xk-b ... xk-1 where b∈{0, ...,k-1}

x的边界是一个真前缀也是一个真后缀。它的长度b称为边界宽。

实例：设x=abacab，那么x的真前缀包括：

ε（空串）,a, ab, aba, abac, abaca

x的真后缀包括：

ε（空串), b, ab, cab, acab, bacab

ε长度为0，边界串ab长度为2

空串ε是所有非空字串的边界串。空串本身没有边界串。

下面的例子演示如何用边界串概念来确定移动距离。

实例：

0123456789...abcabcabd abcabd abcabd

在0...4位置的符号已经匹配了，在位置5对c和d进行比较，发现不匹配。模式串可以被移动3个位置，然后继续在

位置5进行比较。

移动距离由模式串p的匹配前缀的最宽边界串决定。在这个例子中，匹配前缀是abcab，它的长度j=5,

它的最宽的边界串是ab，其宽度b等于2，移动距离等于j-b=5-2=3.

模式串的每个前缀的最宽边界串会在预处理阶段确定下来。这样，在随后的搜索阶段，移动距离就可以通过已经匹配的前缀计算出来。

预处理

定理：假设r, s 是x的边界串，并且|r| < |s|。那么r是s的边界串。

证明：如下图所示，r和s是字串x的边界串。因为r是x的前缀，所以它也是s的真前缀，因为它比s短。

因为r是x的后缀，所有r也是s的真后缀。因此r是s的边界串。

如果s是x的最宽的边界串，那么次宽的边界串r就是s的最宽的边界串。

定义：设x是一个字串，a是A中的一个符号。如果ra是xa的一个边界串，x的边界串r就能够通过a进行扩展。

在预处理阶段会计算一个长度为m+1的数组，每一个元素b[i]包含模式串的长度为i的前缀的最宽边界串的

长度（i=0, ..., m)。因为长度为0的前缀ε没有边界串，我们设置b[0]=-1.

假如b[0], ..., b[i]的值已经知道了，那么b[i+1]的值可以通过检查前缀p0 ...pi-1的边界串是否可以被符号pi 扩展来计算。

如果pb[i] =pi就表示可以扩展（图3）。被检查的边界串可以通过递减顺序使用值b[i], b[b[i]]等获得。

预处理算法由一个变量j构成，j记录着这些值（上述的b[i], b[b[i]]）。如果pj =pi，则宽度为j的边界串就可以被pi扩展。

否则，通过设置j = b[j]. 来检查次宽的边界串。如果没有边界串可以被扩展（j=-1）则循环终止。

通过语句j++递增j后，j就是p0 ... pi的最宽边界串的宽度，这个值被写入b[i+1]中

这解释了，预处理算法和如下搜索算法的相似性。

如果模式串的m个符号都已经匹配了对应的文本窗口(j=m)，函数report就会被调用以报告匹配位置i-j。
随后，模式串被移动最宽边界串允许的最大距离。
下面的例子展示了搜索算法执行的比较，绿色表示匹配，红色表示不匹配。
实例：          
0123456789...  ababbabaa    ababac         ababac         ababac        ababac         ababac

分析
在预处理算法的内部循环中，j的递减值至少是1，因为b[j]<j。当j=-1时，循环终止，因此循环中所递减的j的值最多不超过
由语句j++增加的值。因为j++在外循环中执行了m次，所以内循环的总的执行次数不会超过m次。因此预处理算法的时机复杂
度为O(m)。
类似的分析可知搜索算法的时间复杂度为O(n)。上面的例子说明：比较形成了一个阶梯形状（红色和绿色符号）。整个
楼梯的高度顶多和宽一样，所以最多执行2n次比较。
因为m<=n，所以KMP总的复杂度是O(n)。

其中一种实现
//Searching algorithmint kmpSearch2(const char *t, const char *p){int m=strlen(p), n=strlen(t);int *b = new int[m+1];kmpPreprocess(p, b);int i=0, j=0;while (i<n){while (j>=0 && t[i]!=p[j]) j=b[j];i++; j++;if (j==m){return (i-j);j=b[j];}}return -1;}


 原文：http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm