KMP算法详解(转)
此前一天，一位MS的朋友邀我一起去与他讨论快速排序，红黑树，
字典树，B树、后缀树，包括KMP算法，唯独在讲解KMP算法的时候，言
语磕磕碰碰，我想，原因有二：1、博客内的东西不常回顾，忘了不少；2、
便是我对KMP算法的理解还不够彻底，自不用说讲解自如，运用自如了。
所以，特再写本篇文章。由于此前，个人已经写过关于KMP算法的两篇文
章，所以，本文名为：KMP算法之总结篇。
本文分为如下六个部分：
第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度，并
两相对照各自的匹配原理；第二部分、通过我此前第二篇文章的引用，用
图从头到尾详细阐述KMP算法中的next数组求法，并运用求得的next数
组写出KMP算法的源码；第三部分、KMP算法的两种实现，代码实现一是
根据本人关于KMP算法的第二篇文章所写，代码实现二是根据本人的关于
KMP算法的第一篇文章所写；第四部分、测试，分别对第三部分的两种实
现中next数组的求法进行测试，挖掘其区别之所在；第五部分、KMP完整
准确源码，给出KMP算法的准确的完整源码；第六步份、一眼看出字符串
的next数组各值，通过几个例子，让读者能根据字符串本身一眼判断出
其next数组各值。 力求让此文彻底让读者洞穿此KMP算法，所有原理，
来龙去脉，让读者搞个通通透透（注意，本文中第二部分及第三部分的代
码实现一的字符串下标i
从0开始计算，其它部分如第三部分的代码实现二，第五部分，和第六部分的字符串下标i 皆是从1开始的）。
第一部分、KMP算法初解
1、普通字符串匹配BF算法与KMP算法的时间复杂度比较
KMP算法是一种线性时间复杂的字符串匹配算法，它是对BF算法
（Brute-Force，最基本的字符串匹配算法的）改进。对于给的原始串S
和模式串P，需要从字符串S中找到字符串P出现的位置的索引。
BF算法的时间复杂度O(strlen(S) * strlen(T))，空间复杂度O(1)。
KMP算法的时间复杂度O(strlen(S) + strlen(T))，空间复杂度
O(strlen(T))。
2、BF算法与KMP算法的区别
假设现在S串匹配到i位置，T串匹配到j位置。那么总的来说，两
种算法的主要区别在于失配的情况下，对的值做的处理：
BF算法中，如果当前字符匹配成功，即s[i+j] == T[j]，令j++，
继续匹配下一个字符；如果失配，即S[i
+ j] != T[j]，需要让i++,并且j= 0，即每次匹配失败的情况下，
模式串T相对于原始串S向右移动了一位。
而KMP算法中，如果当前字符匹配成功，即S[i]==T[j]，令i++，
j++，继续匹配下一个字符；如果匹配失败，即S[i]
!= T[j]，需要保持i不变，并且让j = next[j]，这里next[j]
=j -1，即模式串T相对于原始串S向右移动了至少1位(移动的实际
位数j
- next[j]? =1), 同时移动之后，i之前的部分（即S[i-j+1 ~ i-1]），和j=next[j]
之前的部分（即T[0
~ j-2]）仍然相等。显然，相对于BF算法来说，KMP移动更多的位数，
起到了一个加速的作用！
(失配的特殊情形，令j=next[j]导致j==0的时候，需要将i
++，否则此时没有移动模式串)。
3、BF算法为什么要回溯
首先说一下为什么BF算法要回溯。如下两字符串匹配（恰如上面所述：
BF算法中，如果当前字符匹配成功，即s[i+j]
== T[j]，令j++，继续匹配下一个字符）：
i+j（j随T中的j++变，而动）
S：aaaacefghij
T：aaac?
如果不回溯的话就是从下一位开始比起：
aaaacefghij
看到上面红颜色的没，如果不回溯的话，那么从a 的下一位c
比起。然而下述这种情况就漏了（正确的做法当然是要回溯：如果失
配，即S[i +
j] != T[j]，需要让i++,并且j=
aaaacefghij
所以，BF算法要回溯，其代码如下：
view plain int?Index(SString?S,?SString?T,?int?pos)?{?--返回T在S中第
pos个字符之后的位
置?i=pos;?j=1;k=0;?while?(?i?=?S[0]?j?=?T[0]?)?{?if?(S[i+k]?=?=
T[j]){++k;++j;}--继续比较后续字
符?else?{i=i+1;?j=1;?k=0;}?--指针回溯到?下一首位，重新开
始?}?if(jT[0])?return?i;?--子串结束，说明匹配成
功?else?return?0;?}--Index?
不过，也有特殊情况可以不回溯，如下：abcdefghij(主
串)abcdefg(模式串)
即(模式串)没有相同的才不需要回溯。
算法思想
普通的字符串匹配算法必须要回溯。但回溯就影响了效率，回溯是
由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。像
上面所说如果主串为abcdef这样的，大没有回溯的必要。
改进的地方也就是这里，我们从T串本身出发，事先就找准了T自
身前后部分匹配的位置，那就可以改进算法。
如果不用回溯，那模式串下一个位置从哪里开始呢？
还是上面那个例子，T(模式串)为ababc，如果c失配，那就可以往
前移到aba最后一个a的位置，像这样：
这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP
算法所在。这个当T[j]失配后，j
应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串(主串)无关。
5、next数组的含义
重点来了。下面解释一下next数组的含义，这个也是KMP算法中比较
不好理解的一点。
令原始串为: S[i]，其中0=i=n；模式串为: T[j]，其中0=j=m。
假设目前匹配到如下位置
S0,S1,S2.,Si-j,Si-j+1.,Si-1,
Si, Si+1.,Sn
T0,T1.,Tj-1,
S和T的绿色部分匹配成功，恰好到Si和Tj的时候失配，如果要保
持i不变，同时达到让模式串T相对于原始串S右移的话，可以更新j的
值，让Si和新的Tj进行匹配，假设新的j用next[j]表示，即让Si和
next[j]匹配，显然新的j值要小于之前的j值，模式串才会是右移的效
果，也就是说应该有next[j]
= j -1。那新的j值也就是next[j]应该是多少呢？我们观察如下的
匹配：
1)如果模式串右移1位（从简单的思考起，移动一位会怎么样），即
next[j] = j - 1， 即让蓝色的Si和Tj-1匹配
(注：省略号为未匹配部分)
S0,S1,S2.,Si-j,Si-j+1.,Si-1,
Si, Si+1.,Sn
T0,T1.,Tj-1, Tj, . (T的划线部分和S划线部分相等【1】)
T0,T1.Tj-2,Tj-1,
. (移动后的T的划线部分和S的划线部分相等【2】)
根据【1】【2】可以知道当next[j] =j -1，即模式串右移一位的时
候，有T[0
~ j-2] == T[1 ~ j-1]，而这两部分恰好是字符串T[0 ~j-1]的前缀
和后缀，也就是说next[j]的值取决于模式串T中j前面部分的前缀和后
缀相等部分的长度（好好揣摩这两个关键字概念：前缀、后缀，或者再想
想，我的上一篇文章，从Trie树谈到后缀树中，后缀树的概念）。
2)如果模式串右移2位，即next[j] = j - 2， 即让蓝色的Si和
Tj-2匹配?
S0,S1.,Si-j,Si-j+1,Si-j+2.,Si-1,
Si, Si+1.,Sn
T0,T1,T2.,Tj-1,
Tj, .(T的划线部分和S划线部分相等【3】)
T0,T1.,Tj-3,Tj-2.(移动后的T的划线部分和S的划线部分相等【4】)
同样根据【3】【4】可以知道当next[j] =j -2，即模式串右移两位
的时候，有T[0
~ j-3] == T[2 ~ j-1]。而这两部分也恰好是字符串T[0 ~j-1]的前
缀和后缀，也就是说next[j]的值取决于模式串T中j前面部分的前缀和
后缀相等部分的长度。
3)依次类推，可以得到如下结论：当发生失配的情况下，j的新值next[j]取决于模式串中T[0
~ j-1]中前缀和后缀相等部分的长度， 并且next[j]恰好等于这个最
大长度。
!= T[j]，需要保持i不变，并且让j
= next[j]，这里next[j] =j -1，即模式串T相对于原始串S向右移
动了至少1位(移动的实际位数j
- next[j]? =1),
同时移动之后，i之前的部分（即S[i-j+1 ~ i-1]），和j=next[j]
之前的部分（即T[0 ~ j-2]）仍然相等。显然，相对于BF算法来说，KMP
移动更多的位数，起到了一个加速的作用！
(失配的特殊情形，令j=next[j]导致j==0的时候，需要将i ++，否
则此时没有移动模式串)。”
于此，也就不难理解了我的关于KMP算法的第二篇文章之中：“当
匹配到S[i] != P[j]的时候有 S[i-j„i-1] = P[0„j-1]. 如果下面用
j_next去匹配，则有P[0„j_next-1] = S[i-j_next„i-1]
= P[j-j_next„j-1]。此过程如下图3-1所示。
当匹配到S[i] != P[j]时，S[i-j„i-1] = P[0„j-1]：
S: 0 „ i-j „ i-1 i „
P:? 0 „? j-1 j „
如果下面用j_next去匹配，则有P[0„j_next-1] =
S[i-j_next„i-1] = P[j-j_next„j-1]。
所以在P中有如下匹配关系（获得这个匹配关系的意义是用来求next