KMP算法

先从一般的字符串查找算法推导。

现在我们要在字符串S里面查找字符串D，则一般算法是

[plain]

position = 0

WHILE position < S.length //枚举D在S中的位置position

result = Match(S, D, position); //看在position位置上D能匹配S几个字符，从左到右比较匹配

IF (result == D.length) RETURN position; //若D在position上能批评D.length个字符，表示D就出现在这个位置

position += 1; //尝试下一个位置

END

return -1; //没有找到D

这个算法时间复杂度比较高，上界是两个字符串长度的乘积。

我们发现，这个算法有时候做了很多无用功，比如

D = "abcd"

假设 position=0 时， Match(S, D, 0) = 3。那我们肯定知道 S = "abc????..." (?表示未知字母，...表示省略后面的字符)，如果我们下一次让position = 1，就是 "abcd" 和 "bc??" 匹配，直接从第一位就可以看出是不可能相等的（‘a’ != 'b'），所以没有必要尝试这个位置。同样的，position=2时（“abcd" 匹配 "c????"）也不可能相等；position=3时，"abcd" 和 “????” 匹配，有可能相等，才尝试这个位置。

综上所述，在position=0时得到了Match的结果3。我们利用这个结果3，以及D的前三位字符这些信息确定了position=1和2时肯定不可能匹配成功。所以可以直接尝试position=3，减少尝试匹配次数。

充分利用信息，减少不必要的操作。

我们于是想到，利用D的内容，和每次Match的结果（从开头起多少个字符匹配成功），可以推断出position下一次的位置。我们设这个过程为 Next(D, count)，position的尝试变为 position += Next(D, result)。对于上面的情况就是 position=0 时， Match(S, D, position) = 3，Next(D, 3) = 3; position += 3; ==> position=3时blablabla……

即，代码变为

[plain]

position = 0

WHILE position < S.length //枚举D在S中的位置position

result = Match(S, D, position); //看在position位置上D能匹配S几个字符

IF (result == D.length) RETURN position; //若D在position上能批评D.length个字符，表示D就出现在这个位置

position += Next(D, result); //尝试分析得到的下一个位置

END

return -1; //没有找到D

下面问题就是如果设计Next(D, count)这个函数。

我们可以知道在算法运行过程中D不会改变，而count是一个0到D.length的数值。我们求出count = 0 到 D.length 下 Next(D, count) 的值，存到一张表里，每次查表就行了。

即

[plain]

next = GenerateNextTable(D)

position = 0

WHILE position < S.length //枚举D在S中的位置position

result = Match(S, D, position); //看在position位置上D能匹配S几个字符

IF (result == D.length) RETURN position; //若D在position上能批评D.length个字符，表示D就出现在这个位置

position += next[result]; //尝试分析得到的下一个位置

END

return -1; //没有找到D

下面重点就是GenerateNextTable(D)的过程，也就是产生next 数组的过程。next 数组可以简单求出，也可以用更快的算法产生。（由于不会做图，下面有一堆描述，为方便不同种类的阅读，灰色的是说明，可忽略；绿色是定义；红色是算法流程公式；蓝紫色是建议）

如果你尝试了，会知道直接递推出next数组是比较困难的。我们观察发现，若next[i] = k, 则有 D[0..i-k-1] = D[k, i-1]。即把D的前i位拿出来当一个新字符串str，str的前面i-k个字符和str的后面i-k个字符是相等的。而且我们发现，按照next的定义，(i-k)一定是个最大值使str前i-k位和后i-k位相同(k!=0)。因为k相当于position跳过的步数，我们不能跳过有可能匹配的位置。比如说匹配过程中知道S从position开始是这样一个情况abcde???... (没加双引号：字母代表变量字符，而非确定字符；?代表未知字符)，那么若abc = cde，我们就知道position 增加 2 是可以的(abcde... 匹配 cde???...，前三位相同，后面不知道是否相同，可能会匹配成功)，若ab=de，那么position增加3也是可以的，但是我们肯定是让position增加2，因为不能漏掉这个可能。也就是说k有多种可能时取最小，则i-k最大的值。（有点绕，用笔画画会清楚不少）

于是我们定义这样一个操作，对于一个字符串str，它最长有w位前缀等于它的w位后缀，我们称w为str的P值。我们可以知道，next[i] 就等于 i 减去 D[0..i-1 ]的P值（若D[0..i-1]构成的字符串前w位和后w位相同，则若Match结果为i，我们可以直接把position 加上 i-w，请拿纸和笔推导下）。我们先求出每个i，D[0..i-1] 的P值P[i]，然后next[i] = i - P[i]。

求P[i]的话这样做，假设我们知道P[i-1] = k，那么如果 D[i-1] == D[k] 则 P[i] = k+1。（即为新添的一个字符正好等于前缀后面那个字符，请拿纸和笔推导具体下标的产生）。如果D[i-1] != D[k]，看起来会很难办，难道要一个个向前枚举k了么？不，最精华的一点到来了，我们令k=P[k]，继续上面的过程。虽然P[k]所作用的区域已经是D[0..k-1]了，但是我们之前有P[i-1] = k，可以知道D[0..k-1] 和 D[i-1-k..i-2]是相同的，那么D[k-1-P[k]..k-1]也会和D[?..i-2]相同(建议画图理解)。这样减少了k不必要的枚举，且不会漏掉最优解（仔细考虑）。此外我们预设P[0] = -1，k等于-1时令P[i]=0 (k减少到-1意味着P值为0)。

把上面所述红色部分提取出来就能得到next的产生了，时间复杂度是O(n)的，n为D的长度，不证明了，直接给出C语言函数

[C++]

int *GenerateNextTable(const char *D) {// next[i],前i个字符匹配成功，需要前进几步

int L = strlen(D);

int *next = (int *)malloc(sizeof(int) * L);

int P[L+1], i, j;

P[0] = -1;

for (i=1; i<=L; i++) {

j = P[i-1];

while (j>=0 && D[j]!=D[i-1]) {

j = P[j];

}