《数据结构-KMP算法》由会员分享，可在线阅读，更多相关《数据结构-KMP算法（35页珍藏版）》请在金锄头文库上搜索。
1、KMP算法它是：在一个长字符串中匹配一个短子串的无回溯算法。定义s:模式串 ,m:模式串的长度text:要匹配的字符串,n:text的长度设text:x1,x2,xn,s:a1,a2,am,则当存在i使 xi+k=ak(k=1,2,m)时，认为text与模式串匹配，当然text也可能与模式串有多处匹配例如：text:abcabca,s:abc则text与s匹配的位置有3和6朴素算法枚举text中的每一个位置，判断以该位置为起始位置的长度为m的子串是否与s匹配.显然时间复杂度为O(m*n)伪代码如下voidfun(char*text,char*s)for(i=0;texti;i+)for(j=0
2、;jm;j+)if(texti+j!=sj)break;if(j=m)printf(“匹配成功n”);return;printf(“无法匹配n”);KMP算法作为一种无回溯的算法，它是高效的，待会儿你将看到它的时间复杂度为O(m+n)，空间复杂度也为O(m+n)而且，它很容易理解，代码也很短定义next:为对应模式串的数组设字符串为 s1s2s3.sm,其中s1，s2，s3，.si，.sm均是字符，则nexti=m，当且仅当满足如下条件：字符串s1s2.smequals字符串s(i-m+1).si-1si并且s1s2.sms(m+1)unequalss(i-m)s(i-m+1).si-1si。
3、通俗地讲，nexti保存了以si为结尾的后缀与模式串前缀的最长匹配数。定义例如：s:abcabcddeanext:0001230001i=5时，后缀有c,bc,abc,cabc,bcabc,abcabc;相应的前缀为:a,ab,abc,abca,abcab,abcabcs:ababacbnext:0012300KMP算法的运行过程我们用两个指针i和j分别表示，Ai-j+1.i与B1.j完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以Ai结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验Ai+1和Bj+1的关系。如果ai+1=bj+1,i和j各
4、加1，什么时候j=m，就说B是A的子串（B串已经整完了）KMP算法的运行过程如果ai+1!=bj+1,这时候怎么办？i=123456789A=abababaababB=ababacbj=1234567j=5时，ai+1!=bj+1,我们要把j改成比它小的值j。改成多少合适呢？KMP算法的运行过程i=123456789A=abababaababB=ababacbj=1234567记住，我们要保持Ai-j+1.i与B1.j完全相等，因而j是最大的数使ai-j+1.i与B1.j完全相等.KMP算法的运行过程i=123456789A=abababaababB=ababacbj=1234567显然是求一
5、个最长的以i为末尾的后缀要与B的前缀匹配。由于Ai-j+1.i与B1.j完全相等,故令j=nextj即可保证此性质保留KMP算法的运行过程i=123456789A=abababaababB=ababacbj=1234567i=123456789A=abababaababB=ababacbj=1234567KMP算法的运行过程需要注意的是i并没有动，改变的只是j的值如果改变j的值后ai+1仍不等于bj+1的话，继续改变j值直到ai+1=bj+1或者j=0j=0表示i+1前面无论怎么匹配都不能使ai+1=bj+1,只好让ai+1与bj+1单独匹配还是上一个例子，再演示一下KMP算法的运行过程i=1
6、23456789A=abababaababB=ababacbj=1234567当i=6,j=5时，ai+1!=bj+1,故令j=next5=3KMP算法的运行过程i=123456789A=abababaababB=ababacbj=1234567此时i=6,j=3仍不满足ai+1=bj+1，故继续减小j,使j=next3=1KMP算法的运行过程i=123456789A=abababaababB=ababacbj=1234567此时i=6,j=1仍不满足ai+1=bj+1，故继续减小j,使j=next1=0KMP算法的运行过程i=123456789A=abababaababB=ababacbj=
7、1234567终于，A8=B1，i变为8，j为1KMP算法的运行过程i=123456789A=abababadbabB=ababacbj=1234567事实上，有可能j到了0仍然不能满足Ai+1=Bj+1（比如A8=“d”时）。因此，准确的说法是，当j=0了时，我们直接增加i值但忽略j直到出现Ai=B1为止。KMP代码/kmpj=0;for(i=0;i0&ai!=bj)j=nextj-1;if(ai=bj)j+;elsej=0;next数组/nextmemset(next,0,sizeof(next);for(i=1;ibn;i+)temp=nexti-1;while(temp&btemp!=
8、bi)temp=nexttemp-1;if(btemp=bi)nexti=temp+1;elsenexti=0;时间复杂度分析由于while循环的不确定性，好像时间复杂度很高.但事实上，我们可以看到无论是j还是temp，它只在程序的最后+1，故最多+n(+m)。因而while循环最多-n(-m),因而算法的复杂度都是线性的.next的复杂度O(m),KMP的复杂度为O(n)关于next的一个性质问题的提出:关于next的一个性质现在的问题是：如何快速找出S的最小循环周期（循环节）呢？Len是s的长度给出结论：如果len%(len-nextlen-1)=0,则字符串中必存在最小循环节，且循环次数
9、即为 len/(len-nextlen-1)关于next的一个性质证明：必要性：因为字符串中存在最小循环节(设长度为k)，nextlen-1=len-k,所以len%(len-nextlen-1)=0;充分性：令k1=len-nextlen-1,由于k1整除len,所以可以相应的把len划分为n片区域(n=len/(k1)，从小到大依次表示为t1,t2.tn;由next数组的定义可知，t1=t2,t2=t3,.t(n-1)=tn,且相应的片区域即为最小，所以循环次数也为len/(len-nextlen-1);关于next的一个性质例：poj2406题意：给你一串字符串，问它的循环次数Sampl
10、einput:abcdaaaaabababSampleoutput143核心代码如下if(n%(n-nextn-1)=0)printf(%dn,n/(n-nextn-1);elseprintf(1n);关于next的一个性质补充一下：S:abcabcabcan-nextn-1=3,虽然10%3！=0，但是它有理论意义，可以看到若在S后面加上bc，abc就又是最小循环周期了。故这里要注意的是len-nextlen-1为这个串的最小循环节的长度，这不需要最后的子串是完整的；if(len%(lennextlen-1)=0)这个求得的是串的最大的循环的个数这个要求最后的子串是完整的思考KMP不仅仅是匹
11、配完全相等的情况，其思想完全适用于对一定规律的字符进行匹配Eg:http:/poj.org/problem?id=3167关于扩展KMP（了解）我们先比较一下KMP和扩展KMP所表示的意义KMP：next数组的性质是模式串中每一个位置的前缀和此串其实后缀的最大匹配个数kmp匹配时的性质是求出模板串在主串中出现的位置扩展KMP：next数组的性质是模板串中每一个位置的后缀和此串前缀匹配的最大个数kmp匹配的性质是主串中的每个位置和模板串的最多匹配个数。可以看到KMP匹配的是模式串的长度，显然扩展KMP是KMP的一种扩展扩展KMP 像求KMP的next数组一样，我们先求Ai，表示模式串的后缀和模式
12、串的最长公共前缀,然后再利用Ai求出Bi说明一下A的求法，B同理现在我们要求Ai，且A1-Ai-1已经求出，设k，且1=k=i-1，并满足k+Ak最大所以Tk-Tk+Ak-1=T0-TAk-1，推出Ti-Tk+Ak-1=Ti-k-TAk-1令L=Ai-k，若L+i-1k+Ak-1，由A是最长公共前缀知Ai=L，否则，向后匹配，直到字符串失配并相应更新扩展KMP关于复杂度： 很容易看出，在计算的过程中，凡是访问过的点，都不需要重新访问了。一旦比较，都是比较以前从不曾探访过的点开始。因此总的时间复杂度是O(n+m),是线性的。扩展KMP/求模板串中的a数组j=0;while(T0+j=T1+j)j
13、=j+1;intA1=j,k=1;for(inti=2;im;i+)intLen=k+Ak1,L=Ai-k;if(LLen-i+1)Ai=L;elsej=max(0,Len-i+1);while(Ti+j=T0+j)j=j+1;Ai=j，k=i;扩展KMP/求主串中的b数组j=0;while(T0+j=S0+j)j=j+1;intB0=j,k=0;for(inti=1;im;i+)intLen=k+Bk-1,L=Ai-k;if(LLen-i+1)Bi=L;elsej=max(0,Len-i+1);while(Si+j=T0+j)j=j+1;Bi=j，k=i;Hdu3336字符串问题Trie树AC自动机后缀树组hash作业Poj2752Poj2406Hdu1711Poj1961Poj3461Fzu1901Poj2185Hdu1867Hdu3336较难：poj3167
