1、设有主串s和子串t，子串t定位是指在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，把子串t称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t。 传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（nm），其中n和m分别为串s和串t的长度。 KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成为KnuthMorrisPratt算法，简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比，KMP算法的不同点
2、是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（nm）。下面说说KMP算法的原理。KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O（m*n）;KMP匹配算法。可以证明它的时间复杂度为O（m+n）.。一简单匹配算法先来看一个简单匹配算法的函数：int Index_BF （ char S , char T , int pos ）/*若串S中从第pos（S的下标0posS0= S1,S1 != S2,所以S1= T0,S2 != T0.还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊轻况啊。假设S不变，在S中搜
3、索T=“abaabd”呢？答：这种情况，当比较到S2和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和T0间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”呢？这种情况当比较到S2和T2时，发现不等，就去看next2的值，next2=0，意思是S2已经和T2比较过了，不相等，接下来去比较S2和T0吧。假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来去比较S
4、5和T2吧。总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值nextn呢？（本文中next值、模式函数值、模式值是一个意思。三.怎么求串的模式值nextn定义：（1）next0= -1意义：任何串的第一个字符的模式值规定为-1。（2）nextj= -1模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但Tk=Tj）（1kj）。如：T=”abCabCad”则next6=-1，因T3=T6（3）nextj=k模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且Tj != Tk（1k即T0T1T2。Tk-1=Tj-kTj
5、-k+1Tj-k+2Tj-1且Tj != Tk.（1kj）;（4） nextj=0除（1）（2）（3）的其他情况。举例：01）求T=“abcac”的模式函数的值。next0= -1根据（1）next1=0根据（4）因（3）有1=k0但kn,表示,Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？4.其他值，不可能。四.求串T的模式值nextn的函数说了这么多，是不是觉得求串T的模式值nextn很复杂呢？要叫我写个函数出来，目前来说，我宁愿去登天。好在有现成的函数，当初发明KMP算法，写出这个函数的先辈，令我佩服得六体投地。我等后生小子，理解起来，都要反复琢磨。
6、下面是这个函数:void get_nextval（const char *T, int next）求模式串T的next函数值并存入数组next。int j = 0, k = -1;next0 = -1;while （ Tj/*+1*/ ! ）if （k = -1 | Tj = Tk）+j; +k;if （Tj!=Tk）nextj = k;nextj = nextk;/ ifk = nextk;/ while/这里是我加的显示部分/ for（inti=0;ii+）/coutnexti;/coutendl;/ get_nextval另一种写法，也差不多。void getNext（const cha
7、r* pattern,int next）next0=-1;int k=-1,j=0;while（patternjif（k!patternk!patternj ）k=nextk;+k;if（patternk=patternj）nextj=nextk;nextj=k;下面是KMP模式匹配程序，各位可以用他验证。记得加入上面的函数#include string.hint KMP（const char *Text,const char* Pattern） /const表示函数内部不会改变这个参数的值。if（ !Text|!Pattern|Pattern0=|Text0= ）/空指针或空串，返回-1。i
8、nt len=0;const char * c=Pattern;while（*c+!=）/移动指针比移动下标快。+len;/字符串长度。int *next=new intlen+1;get_nextval（Pattern,next）;/求Pattern的next函数值int index=0,i=0,j=0;while（Texti! Patternj!if（Texti= Patternj）+i;继续比较后继字符index += j-nextj;if（nextj!=-1）j=nextj;模式串向右移动j=0;/whiledelete next;if（Patternj=return index;匹配
9、成功int main（）/abCabCadchar* text=bababCabCadcaabcaababcbaaaabaaacababcaabc;char*pattern=adCadCad/getNext（pattern,n）;/get_nextval（pattern,n）;KMP（text,pattern）return 0;五其他表示模式值的方法上面那种串的模式值表示方法是最优秀的表示方法，从串的模式值我们可以得到很多信息，以下称为第一种表示方法。第二种表示方法，虽然也定义next0= -1,但后面绝不会出现-1，除了next0，其他模式值nextj=k（0kj）的意义可以简单看成是：下标
10、为j的字符的前面最多k个字符与开始的k个字符相同，这里并不要求Tj != Tk。其实next0也可以定义为0（后面给出的求串的模式值的函数和串的模式匹配的函数，是next0=0的），这样，nextj=k（0kj）的意义都可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同。第三种表示方法是第一种表示方法的变形，即按第一种方法得到的模式值，每个值分别加1，就得到第三种表示方法。第三种表示方法，我是从论坛上看到的，没看到详细解释，我估计是为那些这样的编程语言准备的：数组的下标从1开始而不是0。下面给出几种方法的例子：表一。（1） next（2） next（3） next第三种表示方法,在我看来，意义不是那么明了，不再讨论。表二。（1）next
