模式串匹配--KMP算法
　前几天百度LBS部门实习二面，让写一个字符串匹配函数，当时忘记KMP怎么写了，就默默的写了一个暴力搜索，连尝试推导一下KMP都没有，结果自然是没有过，以后面试要多和面试官交流，就算忘记了，也要让他知道你试图推导，要不然他会觉得你可能都没有听过。
　　KMP是对前缀暴力搜索的改进，基于的想法其实是很朴素的。首先我们来看一下暴力搜索。
char* BF(char *src, char *pattern){
& & if(src == NULL || pattern == NULL) return NULL;
& & char *src_temp = src, *pattern_temp =
& & while(*src_temp != '\0' && *pattern_temp != '\0'){
& & & & if(*src_temp == *pattern_temp){
& & & & & & src_temp++; pattern_temp++;
& & & & }else{
& & & & & & src_temp = ++
& & & & & & pattern_temp =
& & if(*pattern_temp == '\0')
& & else return NULL;
　　如果匹配失败，则将关键字向右滑动一个字符，从头开始匹配关键字,匹配成功则有src[i,i+1,......i+m] == p[0,1,......m]。BF的时间复杂度是O(m*n)。KMP改进的想法很朴素，能不能不是每次移动一个距离，每次多移动几个距离不就可以提高效率了么，但是每次多移动几个呢？KMP算法就是解决每次移动几个的问题。
　　假设暴力搜索时关键字在匹配到p[j]字符时失败了，即src[i,i+1,......,i+j-1] == p[0,1,......j-1]（1）, src[i+j] != p[j]，则按照暴力搜索的方法将关键字向右滑动一个字符，即从src[i+1]开始从新匹配。
但是我们假设关键串有如下特征：
p[0,1.....j-2] != p[1,2,......j-1]（2），则（1）可知p[0,1......j-2] != src[i+1,i+2,......,i+j-1]，所以将关键串向右滑动一个字符从src[i+1]开始匹配肯定失败，所以在我们知道（2）式的情况下，就可以直接跳过向右滑动一个字符，那到底滑动几个字符呢？如果我们知道了子串p[0,1,......next(j-1)]（next(j-1)又叫做j-1的失效函数），既是p[0,1,......j-1]的最长真前缀又是p[0,1,......j-1]最长后缀，那我们就可以将关键字向右滑动j-1-next(j-1)个字符，并且认为关键串的前next(j-1)个字符已经匹配成功，继续从src[j]开始匹配(这个思想同样应用于求next(j)的算法中，后面的代码中可以看到)。所以整个KMP算法的关键就是求得每一个next(j), j = 0......m，这样就可以知道在j+1匹配失败的时候，应该将关键字向右滑动几个字符位置。可以证明KMP算法的时间复杂度是O(m+n)。
求next(j)的代码如下，相关解释会在注释中：
void next(char *pattern, int *next){
int t = -1; next[0] = -1;
for(int s = 0; pattern[s+1] != '\0'; s++){
while(t & -1 && pattern[t+1] != pattern[s+1]) t = next[t];// t是最长真前缀的下标，s是字符串的下标，这其实就是一个真前缀和后缀的匹配过程，匹配失败则回溯真前缀的真前缀。这也就是KMP的核心思想。
if(pattern[s+1] == pattern[t+1]){
t = t + 1；
next[s+1] =
next[s] = -1;
得到上面的next(j)后，就可以在O(n)的时间内扫描src字符串，以判断该关键串是否出现在其中。关键串沿着匹配字符串滑动，不断尝试将关键字的下一个字符与被匹配字符串的下一个字符匹配，逐步推进。如果在匹配了j个字符后无法匹配，那么将关键字向右滑动j-next(j)个位置，并且前next(j)个字符已经匹配成功，从src[j+1]继续匹配。
char* KMP(char *src, char *pattern){
if(src == NULL || pattern ==
NULL) return NULL;
int pattern_size = 0;
for(; pattern[pattern_size] != '\0'; pattern_size++)
int* next = new int[pattern_size];
next(patter,next);
int s = -1;
for(int i = 0; src[i] != '\0'; i++){
while(s & -1 && src[i] != pattern[s+1]) s = next[s];//匹配失败，则将关键串向右滑动s - next[s]个字符，并且前next[s]个字符已经匹配成功，继续从src[i]开始匹配。
if(src[i] == pattern[s+1]){
if(pattern[s+1] == '\0') return &src[i] - pattern_size +1;
return NULL;
说到KMP就不得不说AC自动机，其实理解了KMP的思想，即找出子串p[0,1,......next(j-1)]，既是p[0,1,......j-1]的最长真前缀又是p[0,1,......j-1]最长后缀，也就不难理解AC自动机。AC自动机又叫Aho-Corasick算法，是Aho和Croasick对KMP算法的，可以在一个文本串种识别一个关键字集合中的任何关键字。由于是关键字集合，所以采用了trie-tree来存储关键字，每个节点的失效函数稍微不同于KMP的失效函数，即状态next(j)对应于最长的、既是串pattern[0,1......,j]的后缀，又是某个关键字的前缀的字符串。对于AC自动机，你可以理解为是在求失效函数和匹配过程中考虑了关键字集合的KMP或者KMP是AC自动机的特例，但是核心思想就是子串p[0,1,......next(j-1)]，既是p[0,1,......j-1]的最长真前缀又是p[0,1,......j-1]最长后缀，AC自动机只是描述关键字集合的一种方法。关于AC自动机，DSQiu的博客/blog/1700312有一个比较好的实现，有兴趣可以看一下。50328人阅读
数据结构与算法（2）
&&&& 个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很&详细&，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数 f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊：
&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& KMP字符串模式匹配详解
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
一.简单匹配算法
先来看一个简单匹配算法的函数：
int Index_BF ( char S [ ], char T [ ], int pos )
/* 若串 S 中从第pos(S 的下标0&pos&StrLength(S))个字符
起存在和串 T 相同的子串，则称匹配成功，返回第一个
这样的子串在串 S 中的下标，否则返回 -1&&& */
int i = pos, j = 0;
while ( S[i+j] != '/0'&& T[j] != '/0')
if ( S[i+j] == T[j] )
j ++; // 继续比较后一字符
i ++; j = 0; // 重新开始新的一轮匹配
if ( T[j] == '/0')
// 匹配成功&& 返回下标
return -1; // 串S中(第pos个字符起)不存在和串T相同的子串
} // Index_BF&&&此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。即从 j=0 起比较 S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的&匹配&，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。
例如：在串S=&abcabcabdabba&中查找T=& abcabd&（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1] 和T[1]是否相等&我们发现一直比较到S[5] 和T[5]才不等。如图：
当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：
这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：
这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：
又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标3。如图：
二. KMP匹配算法
还是相同的例子，在S=&abcabcabdabba&中查找T=&abcabd&，如果使用KMP匹配算法，当第一次搜索到S[5] 和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==&d&的模式函数值（next[5]=2，为什么？后面讲），直接比较S[5] 和T[2]是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。。。最终在S中找到了T。如图：
KMP匹配算法和简单匹配算法效率比较，一个极端的例子是：
在S=&AAAAAA&AAB&(100个A)中查找T=&AAAAAAAAAB&, 简单匹配算法每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1，继续比较。如果使用KMP匹配算法，就不必回溯.
对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为O (m+n)，因此在多数的实际应用场合下被应用。
KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。看前面的例子。为什么T[5]==&d&的模式函数值等于2（next[5]=2），其实这个2表示T[5]==&d&的前面有2个字符和开始的两个字符相同，且T[5]==&d&不等于开始的两个字符之后的第三个字符（T[2]=&c&）.如图：
也就是说，如果开始的两个字符之后的第三个字符也为&d&,那么，尽管T[5]==&d&的前面有2个字符和开始的两个字符相同，T[5]==&d&的模式函数值也不为2，而是为0。
&& 前面我说：在S=&abcabcabdabba&中查找T=&abcabd&，如果使用KMP匹配算法，当第一次搜索到S[5] 和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==&d&的模式函数值，直接比较S[5] 和T[2]是否相等。。。为什么可以这样？
刚才我又说：&（next[5]=2），其实这个2表示T[5]==&d&的前面有2个字符和开始的两个字符相同&。请看图&：因为，S[4] ==T[4]，S[3] ==T[3]，根据next[5]=2，有T[3]==T[0]，T[4] ==T[1]，所以S[3]==T[0]，S[4] ==T[1]（两对相当于间接比较过了），因此，接下来比较S[5] 和T[2]是否相等。。。
有人可能会问：S[3]和T[0]，S[4] 和T[1]是根据next[5]=2间接比较相等，那S[1]和T[0]，S[2] 和T[0]之间又是怎么跳过，可以不比较呢？因为S[0]=T[0]，S[1]=T[1]，S[2]=T[2]，而T[0]&!=&T[1], T[1]&!=&T[2],==&&S[0]&!= S[1],S[1] != S[2],所以S[1]&!= T[0],S[2] != T[0].&还是从理论上间接比较了。
有人疑问又来了，你分析的是不是特殊轻况啊。
假设S不变，在S中搜索T=&abaabd&呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0] 间接比较过了，不相等，接下来去比较S[3]和T[0]吧。
假设S不变，在S中搜索T=&abbabd&呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。
假设S=&abaabcabdabba&在S中搜索T=&abaabd&呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。
总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？（本文中next值、模式函数值、模式值是一个意思。）
三. 怎么求串的模式值next[n]
（1）next[0]= -1&意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1&& 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1&k个字符与开头的1&k
个字符不等（或者相等但T[k]==T[j]）（1&k&j）。
如：T=&abCabCad& 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k&&& 意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] （1&k&j）。
&&&&&&&&&&&&&&&&&&&&&& 即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]&T[j-1]
且T[j] != T[k].（1&k&j）;
(4) next[j]=0&& 意义：除（1）（2）（3）的其他情况。
01）求T=&abcac&的模式函数的值。
&&&& next[0]= -1&根据（1）
&&&& next[1]=0&& 根据 (4)&& 因（3）有1&=k&j;不能说，j=1,T[j-1]==T[0]
&&&& next[2]=0&& 根据 (4)&& 因（3）有1&=k&j;（T[0]=a）!=（T[1]=b）
&&&& next[3]= -1&根据 (2)
&&&& next[4]=1&& 根据 (3)&T[0]=T[3] 且 T[1]=T[4]
若T=&abcab&将是这样：
为什么T[0]==T[3],还会有next[4]=0呢, 因为T[1]==T[4], 根据 (3)& 且T[j] != T[k]&被划入（4）。
02）来个复杂点的，求T=&ababcaabc& 的模式函数的值。
next[0]= -1&&& 根据（1）
&&&&&&&& next[1]=0&&& 根据(4)
&&&&&&&& next[2]=-1&& 根据 (2)
next[3]=0&& 根据 (3) 虽T[0]=T[2] 但T[1]=T[3] 被划入（4）
next[4]=2&& 根据 (3) T[0]T[1]=T[2]T[3] 且T[2] !=T[4]
next[5]=-1&根据 (2)&
next[6]=1&& 根据 (3) T[0]=T[5] 且T[1]!=T[6]
next[7]=0&& 根据 (3) 虽T[0]=T[6] 但T[1]=T[7] 被划入（4）
next[8]=2&& 根据 (3) T[0]T[1]=T[6]T[7] 且T[2] !=T[8]
只要理解了next[3]=0，而不是=1，next[6]=1，而不是= -1，next[8]=2，而不是= 0，其他的好象都容易理解。
03)&& 来个特殊的，求 T=&abCabCad& 的模式函数的值。
next[5]= 0&根据 (3) 虽T[0]T[1]=T[3]T[4],但T[2]==T[5]
next[6]= -1&根据 (2) 虽前面有abC=abC,但T[3]==T[6]
next[7]=4&& 根据 (3) 前面有abCa=abCa,且 T[4]!=T[7]
若T[4]==T[7]，即T=& adCadCad&,那么将是这样：next[7]=0, 而不是= 4,因为T[4]==T[7].
如果你觉得有点懂了，那么
练习：求T=&AAAAAAAAAAB& 的模式函数值，并用后面的求模式函数值函数验证。
&next 函数值究竟是什么含义，前面说过一些，这里总结。
设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],
1.&&&&&& next[n]= -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1] 和T[0]
2.&&&&&& next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。
3.&&&&&& next[n]= k &0 但k&n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？
4.&&&&&& 其他值，不可能。
四. 求串T的模式值next[n]的函数
说了这么多，是不是觉得求串T的模式值next[n]很复杂呢？要叫我写个函数出来，目前来说，我宁愿去登天。好在有现成的函数，当初发明KMP算法，写出这个函数的先辈，令我佩服得六体投地。我等后生小子，理解起来，都要反复琢磨。下面是这个函数:
void get_nextval(const char *T, int next[])
&&&&&& // 求模式串T的next函数值并存入数组 next。
&&&&&& int j = 0, k = -1;
&&&&&& next[0] = -1;
&&&&&& while ( T[j/*+1*/] != '/0' )
&&&&&&&&&&&&& if (k == -1 || T[j] == T[k])
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&& ++j; ++k;
&&&&&&&&&&&&&&&&&&&& if (T[j]!=T[k])
&&&&&&&&&&&&&&&&&&&&&&&&&&& next[j] =
&&&&&&&&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&&&&&&&&& next[j] = next[k];
&&&&&&&&&&&&& }// if
&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&& k = next[k];
&&&&&& }// while
&&& ////这里是我加的显示部分
&& // for(int&i=0;i&j;i++)
&&&&&& //{
&&&&&& //&&&& cout&&next[i];
&&&&&& //}
&&&&&& //cout&&
}// get_nextval　
另一种写法，也差不多。
void getNext(const char* pattern,int next[])
&&&&&& next[0]=&& -1;
&&&&&& int k=-1,j=0;
&&&&&& while(pattern[j]&!=&'/0')
&&&&&&&&&&&&& if(k!=&-1&&&&pattern[k]!=&pattern[j] )
&&&&&&&&&&&&&&&&&&&& k=next[k];
&&&&&&&&&&&&& ++j;++k;
&&&&&&&&&&&&& if(pattern[k]==&pattern[j])
&&&&&&&&&&&&&&&&&&&& next[j]=next[k];
&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&& next[j]=k;
&&&&&& ////这里是我加的显示部分
&& // for(int&i=0;i&j;i++)
&&&&&& //{
&&&&&& //&&&& cout&&next[i];
&&&&&& //}
&&&&&& //cout&&
下面是KMP模式匹配程序，各位可以用他验证。记得加入上面的函数
#include &iostream.h&
#include &string.h&
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
&&&&&& if( !Text||!Pattern||&Pattern[0]=='/0'&||&Text[0]=='/0' )//
&&&&&&&&&&&&& return -1;//空指针或空串，返回-1。
&&&&&& int len=0;
&&&&&& const char * c=P
&&&&&& while(*c++!='/0')//移动指针比移动下标快。
&&&&&& {&&&&
&&&&&&&&&&&&& ++//字符串长度。
&&&&&& int *next=new int[len+1];
&&&&&& get_nextval(Pattern,next);//求Pattern的next函数值
&&&&&& int index=0,i=0,j=0;
&&&&&& while(Text[i]!='/0'&&& Pattern[j]!='/0' )
&&&&&&&&&&&&& if(Text[i]== Pattern[j])
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&& ++i;// 继续比较后继字符
&&&&&&&&&&&&&&&&&&&& ++j;
&&&&&&&&&&&&& }
&&&&&&&&&&&&& else
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&& index += j-next[j];
&&&&&&&&&&&&&&&&&&&& if(next[j]!=-1)
&&&&&&&&&&&&&&&&&&&&&&&&&&& j=next[j];// 模式串向右移动
&&&&&&&&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&& j=0;
&&&&&&&&&&&&&&&&&&&&&&&&&&& ++i;
&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&& }
&&&&&& }//while
&&&&&& delete []
&&&&&& if(Pattern[j]=='/0')
&&&&&&&&&&&&&// 匹配成功
&&&&&& else
&&&&&&&&&&&&& return -1;&&&&&&
int main()//abCabCad
&&&&&& char* text=&bababCabCadcaabcaababcbaaaabaaacababcaabc&;
&&& char*pattern=&adCadCad&;
&&&&&& //getNext(pattern,n);
&&& //get_nextval(pattern,n);
&&&&& cout&&KMP(text,pattern)&&
&&&&&& return 0;
五．其他表示模式值的方法
上面那种串的模式值表示方法是最优秀的表示方法，从串的模式值我们可以得到很多信息，以下称为第一种表示方法。第二种表示方法，虽然也定义next[0]= -1,但后面绝不会出现-1，除了next[0]，其他模式值next[j]=k(0&k&j)的意义可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同，这里并不要求T[j] != T[k]。其实next[0]也可以定义为0（后面给出的求串的模式值的函数和串的模式匹配的函数，是next[0]=0的），这样，next[j]=k(0&k&j)的意义都可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同。第三种表示方法是第一种表示方法的变形，即按第一种方法得到的模式值，每个值分别加1，就得到第三种表示方法。第三种表示方法，我是从论坛上看到的，没看到详细解释，我估计是为那些这样的编程语言准备的：数组的下标从1开始而不是0。
&下面给出几种方法的例子：
&&&&& 表一。
第三种表示方法,在我看来，意义不是那么明了，不再讨论。
&&&&&&&&&& 表二。
&&&&& 表三。
对比串的模式值第一种表示方法和第二种表示方法，看表一：
第一种表示方法next[2]= -1,表示T[2]=T[0]，且T[2-1] !=T[0]
第二种表示方法next[2]= 0,表示T[2-1] !=T[0],但并不管T[0] 和T[2]相不相等。
第一种表示方法next[3]= 0,表示虽然T[2]=T[0]，但T[1] ==T[3]
第二种表示方法next[3]= 1,表示T[2] =T[0],他并不管T[1] 和T[3]相不相等。
第一种表示方法next[5]= -1,表示T[5]=T[0]，且T[4] !=T[0]，T[3]T[4] !=T[0]T[1]，T[2]T[3]T[4] !=T[0]T[1]T[2]
第二种表示方法next[5]= 0,表示T[4] !=T[0]，T[3]T[4] !=T[0]T[1] ，T[2]T[3]T[4] !=T[0]T[1]T[2]，但并不管T[0] 和T[5]相不相等。换句话说：就算T[5]==&x&,或 T[5]==&y&,T[5]==&9&,也有next[5]= 0 。
从这里我们可以看到：串的模式值第一种表示方法能表示更多的信息，第二种表示方法更单纯，不容易搞错。当然，用第一种表示方法写出的模式匹配函数效率更高。比如说，在串S=&adCadCBdadCadCad 9876543&中匹配串T=&adCadCad&, 用第一种表示方法写出的模式匹配函数,当比较到S[6] != T[6] 时，取next[6]= -1（表三）,它可以表示这样许多信息： S[3]S[4]S[5]==T[3]T[4]T[5]==T[0]T[1]T[2]，而S[6] != T[6]，T[6]==T[3]==T[0]，所以S[6] != T[0],接下来比较S[7]和T[0]吧。如果用第二种表示方法写出的模式匹配函数,当比较到S[6] != T[6] 时，取next[6]= 3（表三）,它只能表示：S[3]S[4]S[5]== T[3]T[4]T[5]==T[0]T[1]T[2]，但不能确定T[6]与T[3]相不相等，所以，接下来比较S[6]和T[3];又不相等，取next[3]= 0，它表示S[3]S[4]S[5]== T[0]T[1]T[2]，但不会确定T[3]与T[0]相不相等，即S[6]和T[0] 相不相等，所以接下来比较S[6]和T[0]，确定它们不相等，然后才会比较S[7]和T[0]。是不是比用第一种表示方法写出的模式匹配函数多绕了几个弯。
为什么，在讲明第一种表示方法后，还要讲没有第一种表示方法好的第二种表示方法？原因是：最开始，我看严蔚敏的一个讲座，她给出的模式值表示方法是我这里的第二种表示方法，如图：
她说：&next 函数值的含义是：当出现S[i] !=T[j]时，下一次的比较应该在S[i]和T[next[j]]&之间进行。&虽简洁，但不明了，反复几遍也没明白为什么。而她给出的算法求出的模式值是我这里说的第一种表示方法next值，就是前面的get_nextval()函数。匹配算法也是有瑕疵的。于是我在这里发帖说她错了：
&& 现在看来，她没有错，不过有张冠李戴之嫌。我不知道，是否有人第一次学到这里，不参考其他资料和明白人讲解的情况下，就能搞懂这个算法（我的意思是不仅是算法的大致思想，而是为什么定义和例子中next[j]=k(0&k&j)，而算法中next[j]=k(-1&k&j)）。凭良心说：光看这个讲座，我就对这个教受十分敬佩，不仅讲课讲得好，声音悦耳，而且这门课讲得层次分明，恰到好处。在KMP这个问题上出了点小差错，可能是编书的时候，在这本书上抄下了例子，在那本书上抄下了算法，结果不怎么对得上号。因为我没找到原书，而据有的网友说，书上已不是这样，也许吧。说起来，教授们研究的问题比这个高深不知多少倍，哪有时间推演这个小算法呢。总之，瑕不掩玉。
书归正传，下面给出我写的求第二种表示方法表示的模式值的函数,为了从S的任何位置开始匹配T，&当出现S[i] !=T[j]时，下一次的比较应该在S[i]和T[next[j]]&之间进行。&&&& 定义next[0]=0 。
&void myget_nextval(const char *T, int next[])
&&&& // 求模式串T的next函数值（第二种表示方法）并存入数组 next。&&&&&&&&&&&&&&&&
&&&& int j = 1, k = 0;
&&&& next[0] = 0;
&&&&&& while ( T[j] != '/0' )
&&&& {&&&&
&&&&&&&&&&&&&&&&&& if(T[j] == T[k])
&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&& &&&&& next[j] =
&&&&&&&&&&&&&&&&&& &&&&& ++j; ++k;&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&&& else if(T[j] != T[0])
&&&&&&&&&&&&&&&&&& {
&&&&& &&&&&&&&&&&&next[j] =
&&&&&&&&&&&&&&&&& ++j;
&&&&&&&&&&&&&&&&&&&&&&&&& &k=0;
&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&& next[j] =
&&&&&&&&&&&&&&&&& ++j;
&&&&&&&&&&&&&&&&&&&&&&&&& && k=1;
&&&&&&&&&&&&&&&&&& }
&&&& }//while
&&& for(int&i=0;i&j;i++)
&&&&&&&&&&& cout&&next[i];
&&&& cout&&
}// myget_nextval
下面是模式值使用第二种表示方法的匹配函数（next[0]=0）
int my_KMP(char *S, char *T, int pos)
int i = pos,&j = 0;//pos(S 的下标0&pos&StrLength(S))
while ( S[i] != '/0' && T[j] != '/0' )
&&& if (S[i] == T[j] )
&&&&&&&& ++i;
&&&&&&&&&&& &++j; // 继续比较后继字符
&& else&&&&&&&&&&&& // a&b&a&b&c&a&a&b&c
&&&& &&&&&&&&&&&&&& // 0&0&0&1&2&0&1&1&2
&& {&&&&&&&&&&&&& //-1&0&-1&0&2 -1&1&0&2
&&&& &i++;
&&&& j = next[j];&&&& /*当出现S[i] !=T[j]时，
&&&& &&&&&&&& 下一次的比较应该在S[i]和T[next[j]]&之间进行。要求next[0]=0。
在这两个简单示范函数间使用全局数组next[]传值。*/
if ( T[j] == '/0' )
&&& return (i-j); // 匹配成功
&&&& return -1;
} // my_KMP
六．后话--KMP的历史
[这段话是抄的]
Cook于1970年证明的一个理论得到，任何一个可以使用被称为下推自动机的计算机抽象模型来解决的问题，也可以使用一个实际的计算机（更精确的说，使用一个随机存取机）在与问题规模对应的时间内解决。特别地，这个理论暗示存在着一个算法可以在大约m+n的时间内解决模式匹配问题，这里m和n分别是存储文本和模式串数组的最大索引。Knuth 和Pratt努力地重建了 Cook的证明，由此创建了这个模式匹配算法。大概是同一时间，Morris在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这里可以看到并不是所有的算法都是&灵光一现&中被发现的，而理论化的计算机科学确实在一些时候会应用到实际的应用中。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：350567次
积分：3818
积分：3818
排名：第7953名
原创：44篇
转载：16篇
评论：128条
(2)(1)(1)(4)(2)(2)(14)(1)(2)(4)(4)(9)(22)(1)KMP 字符串匹配经典算法深度解析
摘要：KMP算法是字符串匹配的经典算法，由于其O(m+n)的时间复杂度，至今仍被广泛应用。大道至简，KMP算法非常简洁，然而，其内部却蕴含着玄妙的理论，以至许多人知其然而不知其所以然。本文旨在解开KMP算法的内部玄妙所在，希望能够有助于学习与理解。 & 1、KMP算法 &&& 一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此称之为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作，其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离，继续进行比较。 & 2、基于有限自动机理解算法 &&& KMP 算法看似简单，其实要完全理解还是有困难的。KMP算法其实可以看成是一个有限自动机，分为 2 部分：第一部分自动机的构造 ( 对应一般的说法就是失效函数，转移函数， overlap 函数 ) ，第二部分在自动机上搜索过程。举个例子： 目标串 T = 模式串 P=abaabcac ；根据模式串构造自动机，向前的箭头表示搜索前进的方向。向后的箭头表示不匹配的回溯，即失效函数，或者状态变迁函数。例如： &f(j=1) = 0; &f(j=2) = 0; &f(j=3) = 1; &f(j=4) = 1; &f(j=5) = 2; &f(j=6) = 0; &f(j=7) = 1; &&& KMP本质上是构造了DFA并进行了模拟，因此很显然一旦从模版T构造了自动机D，用D去匹配主串S的过程就是线性的。KMP最引人入胜的地方就在于构造D的自匹配过程，它充分利用了D是一个DAG的性质，使得构造过程也是线性的。KMP算法不需要计算变迁函数，只用到辅助数组Next，即模式串自身的特征向量。特征向量可以用模式与其自身进行比较，预先计算出来，它可用于加快字符串匹配算法与有限自动机匹配器的执行速度。
&&& 3、Next特征数组构造 &&& 模式串P开头的任意个字符，把它称为前缀子串，如p0p1p2…pm-1。在P的第i位置的左边，取出k个字符，称为i位置的左子串，即pi-k+1... pi-2 pi-1 pi。求出最长的（最大的k）使得前缀子串与左子串相匹配称为，在第i位的最长前缀串。第i位的最长前缀串的长度k就是模板串P在位置i上的特征数n[i]特征数组成的向量称为该模式串的特征向量。 && 可以证明对于任意的模式串p=p0p1…pm-1,确实存在一个由模式串本身唯一确定的与目标串无关的数组next，计算方法为： && (1)& 求p0…pi-1中最大相同的前缀和后缀的长度k; && (2)& next[i] = && 作为特殊情况，当i=0时，令next[i] = -1;显然，对于任意i(0≤i&m)，有next[i] &假定已经计算得到next[i], 那么next[i+1] = ? 特征数ni ( -1≤ ni ≤ i )是递归定义的，定义如下： && (1) n[0] ＝ -1，对于i & 0的n[i] ，假定已知前一位置的特征数 n[i-1]＝ k ； && (2) 如果pi ＝ pk ，则n[i] ＝ k＋1 ； && (3) 当pi ≠ pk 且k≠0时，则令k ＝ n [k -1] ; 让(3)循环直到条件不满足； && (4) 当qi ≠ qk 且k ＝ 0时，则ni ＝ 0; && 根据以上分析，可以得到Next特征数组的计算方法，算法代码如下：
void get_next(SString T, int &next[])
//求模式串T的next函数值并存入数组next
i = 1; next[1] = 0; j = 0;
while (i & T[0])
if(j ==0 || T[i] == T[j])
++i; ++j; next[i] =
j = next[j];
文献[5]中解释了以上计算方法存在一定缺陷，存在多比较的情况，可对其进行修正，得到如下算法：
void get_next(SString T, int &next[])
//求模式串T的next函数值并存入数组next
i = 1; next[1] = 0; j = 0;
while (i & T[0])
if(j ==0 || T[i] == T[j])
if (T[i] != T[j])
next[i] = next[j];
j = next[j];
4、算法实现
&& KMP算法的难点就是有限自动机的构造和特征向量的计算。解决了这两个问题后，具体匹配算法就很简单了。
Index_KMP(SString
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。
//其中，T非空，1≤pos≤StrLength(S)。
while(i &= S[0] && j&= T[0]){
if(j == 0 || S[i] == T[j]) { ++i; ++j; }//继续比较后继字符
j = next[j];//模式串象右移动
if(j&T[0])
i-T[0];//匹配成功
}//Index_KMP
&&& 算法相关理论分析与证明，以及算法复杂性分析，若感兴趣请参考文献[3]、[4]、[5]，这里不再赘述。
5、参考文献 [1]& [2]&和extend-kmp算法.html& [3] KMP算法讲义PPT(Hu Junfeng, Peking University) [4] 算法导论(第32章 字符串匹配) [5] 数据结构(第4章 串)