《KMP算法详解-转帖.docx》由会员分享，可在线阅读，更多相关《KMP算法详解-转帖.docx（10页珍藏版）》请在课桌文档上搜索。
1、KMP算法详解转帖2010-02-2412:05个人觉得这篇文章是网上的介绍有关KMP算法更让人简洁理解的文章的确说得很“具体”，耐性地把它看完确定会有所收获的另外有关模式函数值nexti的确仃很多版本啊.在另外些面对对象的算法描述书中也仃失效函数f(j)的说法,其实是个意思，Pnextj=f(j-l)b不过还是nextj这种表示法好理解啊：KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符印中定位另一个串的高效第法。简洁匹配算法的时间困难度为0(m*n);KMP匹配兑法。可以证明它的时间困难度为0(m+n).。.简洁匹配算法先来看一个简洁匹配算法的函数：intIndexB
2、F(ChHrS,charT,inipos)I/*若用S中从第POS(S的下标OWpOSGtr1.ength(三)个字符起存在和申T相同的子串，则称匹配胜利，返回第一个这样的子串在串S中的下标，否则返回-1*/inti=pos,j=0:while(Si+j!=0,UTj!=,0,)if(Si+j=Tj)j+；/接着比较后一字符else(i+;j=0：/重新起先新的一轮匹配)if(Tj=,0,)returni;/匹配胜利返回下标elsereturnT;串S中(第pos个字符起)不存在和串T相同的子串)/IndeX_BF此算法的思想是直截了当的:将主串S中某个位置i起始的了用和模式串T相比较。即从j
3、=0起比较Si+j与TlJ,若相等,则在主申S中存在以i为起始位置匹配胜利的可能性，接着往后比较(j逐步增1),直至与T串中最终一个字符相等为止，否则改从S串的卜.一个字符起重新起先进行卜.一轮的匹配”,即将用T向后滑动位，即i增1,而j退回至0,重新起先新轮的匹配，例如：在申S=abcabcabdabba”中查找T=abcabd(我们可以假设从下标0起先):先是比较S0和T0是否相等,然后比较SI：1和Tl是否相等我们发觉始终比较到S5和T5才不等。如图：当这样个失配发生时，T下标必需回溯到起先，S下标回溯的长度与T相同.然后S下标增1,然后再次比较。如图：这次立即发生了失配，T下标又回溯到
4、起先，S下标增I,然后再次比较。如图：这次立即发生/失配，T下标又回溯到起先，S下标增I,然后再次比较.如图：乂次发生了失配，所以T下标乂回溯到起先，S下标增1,然后再次比较。这次T中的全部字符都和s中相应的字符匹配函数返I可T在S中的起始下标3。如图:二.KMP匹配算法还是相同的例子，在S=abcabcabdabba”中查找T=abcabd”,假如运用KMP匹配算法，当第次搜寻到S5和T5不等后，S下标不是回溯到1,T下标也不是回溯到起先，而是依据T中T5=-d的模式函数值(ncxt5=2,为什么？后面讲)，干脆比较S5和T2是否相等，因为相等，S和T的下标同时增加：因为乂相等，S和T的下标
5、乂同时增加。最终在S中找到了T。如图：KMP匹配算法和简洁匹配算法效率比较，个极端的例子是：在S=ttAAAAAA-AAB“(100个A)中查找T=,AAAAAAAAB,t,简洁匹配算法每次都是比较到T的结尾，发觉字符不同，然后T的下标回溯到起先，S的下标也要回溯相同长度后增1，接着比较。假如运用KMP匹配算法,就不必回溯.对于般文稿中用的匹配，简洁匹配算法的时间困难度可降为O(In-n),因此在多数的实际应用场合下被应用.KYP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。看前面的例子。为什么T5k=d的模式函数值等于2(nexc5=2),其实这个2表示T5=d的前面有2个
6、字符和起先的两个字符相同，IlT5=fd不等于起先的两个字符之后的第1个字符(T2=c).如图：也就是说，假如起先的两个字符之后的第三个字符也为d,那么，尽管T5=d的前面有2个字符和起先的两个字符相同，T5=三(T的模式函数值也不为2,而是为0。前面我说：在S=”abcabcabdabba”中查找T=abcabd”，假如运用KMP匹配算法，当第次搜寻到S5和T5不等后，S下标不是回溯到1.T下标也不是回溯到起先，而是依据T中T5=d的模式函数值,干脆比较S5和T2是否相等.。.为什么可以这样？刚才我又说:“(next5=2),其实这个2表示T5三=d的前面有2个字符和起先的两个字符相同.请看
7、图：因为,S4=T4,S3=T3,依据next5=2,有T3=T0,T4=T1,所以S3=T0,S4T1(两对相当于间接比较过了)，因此，接卜.来比较S5和T2J是否相等。有人可能会问:S3flT0,S4和TuJ是依据nexl5=2间接比较相等，那S1.flT0,S2和T和之间又是怎么跳过,可以不比较呢?因为SO=TO,S1=T1,S2=T2,而T0!=T1,Tl!=T2,=S0!=S1,S1!=S2,所以Sl!=T0,S2!=T0.还是从理论上间接比较了。有人疑问乂来了，你分析的是不是特殊轻况啊。假设S不变，在S中搜寻T=abaabd”呢?答：这种状况，当比较到S2和T2时，发觉不等,就去看
8、nexl2的值，next发=T,意思是S2已经和T0间接比较过了,不相等，接下来去比较S3和T接吧。假设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的起先两个相等，接下来去比较S5和T吧总之，有了用的next值，切搞定。那么，怎么求串的模式函数值nextn呢
9、？(本文中next值、模式函数值、模式值是个意思。)三.怎么求串的模式值nexln定义：(1) next0三-1意义：任何串的第一个字符的模式值规定为-1.(2) ncxtj=-1意义：模式小T中下标为j的字符，假如与首字符相同，且的前面的lk个字符与开头的lk个字符不等(或者相等但kI=T1.jD(IWkQ).如:T=abCabCad”则next6=T,因T3=T6(3)nextj=k意义：模式串T中下标为j的字符，假如的前面k个字符号开头的k个字符相等，且Tj!=Tklkj).BPTt0TlT2.,Tk-1=Tj-kTj-k+lTj-k+2Tj-l且Tj!=Tk.(lkj);(4)next
10、j=O意义：除(1)(2)(3)的其他状况。举例：01)求T=abcac”的模式函数的值。next0=T依据(1)因(3)仃l=kj;不能说，因(3)有l=k0但kn,表示,Sm的前k个字符与T中的起先k个字符已经间接比较相等r,下一次比较sm和Tk相等吗？4. 其他值，不行能。四.求串T的模式值nextn的函数说这么多，是不是觉得求串T的模苴值nextn很困难呢？要叫我写个函数出来，目前来说，我宁愿去登天.好在有现成的函数，当时独创KMP算法，写出这个函数的先辈，令我佩服得六体投地。我等后生小子，理解起来，都要反贪琢磨。下面是这个函数：voidget_nextval(constchar*T,
11、intnext)(求模式串T的next函数值并存入数组next。intj=0,k=-1:ncxt0=-1：whiIe(TCj/*+!*/!=0,)(if(k=-1HTj=Tk)+j;+k;if(Tj!=Tk)nextj=k;elsenextj=nextk:/ifelsek=nextk;/while这里是我加的显示部分/for(inti=0：ij;i+)/coutnexli;/coutendl:)/goJncxtval另一种盲法，也差不多。voidgetNext(constchar*pattern,int11ext)(noxt0=-1;intk=-l,j=0;whiIe(patternj!=0)
12、if(k!=-1&patternk!=patternj)k=nextk;+j；+k;if(patternk=patternj)ncxtj=ncxtk;else11extj=k;)这里是我加的显示部分/for(inti=0;ij;i+)/coutnexti：/coutendl:)卜面是KMp模式匹配程序，各位可以用他独证。记得加入上面的函数PincludcWinCIUdeintKMP(constchar*Texl,constchar*Pattern)/const表示函数内部不会变更这个参数的值。(if(!Text!Pattern!Paltern0=t0Texl=,O,)/returnT;/空指针
13、或空串，返回-1。intIen=O:constchar*C=Pattern;While(*c+!=0D移动指针比移动下标快。(+Icn;/字符串长度。)int*nexl=newintlen+l;get_nextval(Pattern,next);求Pattern的next函数值intindex=0,i=0,j=0;while(Texti!=0&Patternj!=0)(if(Texti=Patternj)(i;/接着比较后继字符+j；else(index+=j-nextj：if(nextj!=-l)j=nextj:/模式串向右移动else(j=0：+i：J)whiIedeletenexl;if
14、(Patternj=0)returnindex;/匹配胜利elsereturn-I;)intmainO/ZabCabCad(char*texl=bababCubCudcuabcuababcbaHHabuaacHbabcuabc;Char*pattern=adCadCad”：/ZgetNext(pattern,n)：/gelnexlval(pattern,n);coutKMP(text,pattern)endl;return0：)五.其他表示模式值的方法上面那种串的模式值表示方法是最优秀的丧示方法，从串的模式值我们可以得到很多信息，以下称为第种表示方法。其次种表示方法,虽然也定义next0=T,
15、但后面绝不会出现7,除了next0,其他模式值nextj=k(OWkj)的意义可以简洁看成是：下标为j的字符的前面最多k个字符与起先的k个字符相同，这里并不要求Tj!=Tk.其实next0也可以定义为0(后面给出的求串的模式值的函数和串的模式匹配的函数，是nextO=O的),这样,ncxtj=k(OWkj)的意义都可以简洁看成是：下标为j的字符的前面最多k个字符与起先的k个字符相同。第三种表示方法是第一种表示方法的变形，即按第一种方法得到的模式值，每个值分别加1，就得到第三种表示方法。第三种表示方法，我是从论坛上看到的，没看到具体说明，我估计是为那些这样的编程语言打算的：数组的下标从1起先而不
16、是0.下面给出几种方法的例子：表一。下标012345678Tababcaabc(1) next-10-102-1102(2) next-100I201I2(3) next010130213第三种表示方法,在我看来，意义不是那么明白，不再探讨。表二。下标01234TabcAc(Dnext-100-11(2)next-10001表三。下标01234567TadCadCad(Dnext-100-100-10(2)next-10001234对比串的模式值第一种表示方法和其次种表示方法，看表一：第一种表示方法next2=T,表示T2=T0,T2-1!=T0其次种表示方法nexi2-0,表示T2T!=T0
17、,但并不管T0和T2相不相等。第一种表示方法next3=0,表示虽然T2=T0,但Tl=T3其次种表示方法next3=1,表示表2=T0,他并不管Tl和T3相不相等。第一种表示方法nexl5=T,表示T5=T0,且T!=T,T3T4!=TOT1,T2T3T4!=T0TlT2其次种表示方法next5=0,表示T4!=T0,T3T4!=TOT1.T2T3T4!=TOT1T2,但并不管T0和T5相不相等.换句话说:就算T5=x,或T5=y,T5=9,也有nexl5=0.从这里我们可以看到：串的模式值第一种表示方法能表示更多的信息，其次种表示方法更单纯，不简洁搞错。当然，用第种表示方法写出的模式匹配函
18、数效率更氤比如说,在申S1.“adCadCBdadCadCad9876543”中匹配串T=adCadCad”，用第一种表示方法写出的模式匹配函数，当比较到S6!=T6时，取nexl6=T（表三），它可以表示这样很多信息：S3S4S5=T3T4T5=T0TlT2,而S6!=T6,T6=T3=T0,所以S6!=T0,接下来比较所7和T0吧.假如用其次种表示方法写出的模式匹配函数，当比较到S6!=T6时，取nexl6=3（表三），它只能表示：S3S4S5=T3T4T5=T0TlT2,但不能确定T6与T3相不相等，所以，接下来比较S6和T3;又不相等,取next3=0,它表示S3S4S5=TOT1T2
19、,但不会确定T3与T0相不相等，即S6和T0相不相等，所以接下来比较S6和T0,确定它们不相等，然后才会比较S7和T0.是不是比用第一种表示方法写出的模式匹配函数多绕了几个弯。为什么，在讲明第一种表示方法后，还要讲没有第一种表示方法好的其次种表示方法？缘由是：最起先，我看严蔚敏的一个讲座，她给出的模式值表示方法是我这里的其次种表示方法，如图：她说：“next函数值的含义是：当出现Si!=TjB4,下次的比较应当在Si和Tncxtj之间进行“虽简洁，但不明白，反复几通也没明白为什么.而她给出的算法求出的模式值是我这里说的第一种表示方法next(ft,就是前面的gelnextval()函数。匹配算
20、法也是有瑕疵的。于是我在这里发帖说她错了：现在看来，她没有错，不过有张冠李戴之嫌。我不知道，是否有人第次学到这里，不参考其他资料和明白人讲解的状况下，就能搞懂这个算法(我的意思是不仅是.算法的大致思想，而是为什么定义和例子中nextj-k(O这kj),而算法中nextj=k(T茎kj)。凭良心说：光看这个讲座，我就对这个教受非常钦做，不仅讲课讲得好，声音悦耳，而且这门课讲得U次分明，恰到好处.在KMP这个问选上出了点小差错，可能是编书的时候，在这本书上抄下了例子，在那本书上投下了算法，结果不怎么对得上号。因为我没找到原书，而据有的网友说，书上已不是这样，或许吧。说起来.教授们探讨的问题比这个高
21、深不知多少倍，哪有时间推演这个小算法呢。总之，瑕不掩玉。书归正传，下面给出我写的求其次种表示方法表示的模式值的函数,为了从S的任何位置起先匹配T,“当出现Si!=TjRt,下一次的比较应当在Si和Tnextj之间进行。”定义next0=0。voidmyget_nextval(constchar*T,intnext)(求模式串T的nexl函数值(其次种表示方法)并存入数组next。intj=1,k-0;nexl0=0;while(Tj!=,0,)(if(Tj=Tk)(11extj=k：Hj坎elseif(Tj!=T)(nextj=k：+；k=0;)else(nextj=k:+j；k=l;)/wh
22、ilefor(inti=O;ij;i+)coutnexti;)coutendl;)/myget_nextval下面是模式值运用其次种表示方法的匹配函数(next0=0)intmyKMP(char*S,char*T,intpos)(inti=pos,j=0pos(S的下标OWpOS0,)return(i-j)：/匹配胜利elsereturn_1;)/叽KMP六.后话一KMP的历史这段话是抄的CoOk于1970年证明的一个理论得到，任何一个可以运用被称为下推自动机的计算机抽象模型来解决的问题，也可以运用一个实际的计算机(更精确的说，运用个随机存取机)在与问题规模对应的时间内解决。特殊地,这个理论示意存在若一个算法可以在大约m+n的时间内解决模式匹配问题，这里m和n分别是存储文本和模式串数组的最大索引。Knulh和Pratt努力地重建了COok的证明，由此创建了这个模式匹配算法。或许是同一时间，NorriS在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这里可以看到并不是全部的算法都是“灵光一现”中被发觉的，而理论化的计钵机科学的确在一些时候会应用到实际的应用中。本文来自CSDN博客,转文请标明出处:
