KMP算法

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;text[i];i++){for(j=0;jm;j++)if(text[i+j]!=s[j])break;if(j==m){printf(“匹配成功\n”);return;}}printf(“无法匹配\n”);}KMP算法•作为一种无回溯的算法，它是高效的，待会儿你将看到它的时间复杂度为O(m+n)，空间复杂度也为O(m+n)•而且，它很容易理解，代码也很短定义•next:为对应模式串的数组•设字符串为s1s2s3...sm,其中s1，s2，s3，...si，...sm均是字符，则next[i]=m，当且仅当满足如下条件：字符串s1s2...smequals字符串s(i-m+1)...si-1si并且s1s2...sms(m+1)unequalss(i-m)s(i-m+1)...si-1si。•通俗地讲，next[i]保存了以s[i]为结尾的后缀与模式串前缀的最长匹配数。定义•例如：•s:abcabcddea•next:0001230001•i=5时，后缀有c,bc,abc,cabc,bcabc,abcabc;•相应的前缀为:a,ab,abc,abca,abcab,abcabc•s:ababacbnext:0012300KMP算法的运行过程•我们用两个指针i和j分别表示，A[i-j+1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。•如果a[i+1]==b[j+1],i和j各加1，什么时候j==m，就说B是A的子串（B串已经整完了）KMP算法的运行过程•如果a[i+1]!=b[j+1],这时候怎么办？•i=123456789……•A=abababaabab…•B=ababacbj=1234567j=5时，a[i+1]!=b[j+1],我们要把j改成比它小的值j‘。改成多少合适呢？KMP算法的运行过程•i=123456789……•A=abababaabab…•B=ababacbj=1234567•记住，我们要保持A[i-j+1..i]与B[1..j]完全相等，因而j’是最大的数使a[i-j’+1..i]与B[1..j’]完全相等.KMP算法的运行过程•i=123456789……•A=abababaabab…•B=ababacbj=1234567•显然是求一个最长的以i为末尾的后缀要与B的前缀匹配。由于A[i-j+1..i]与B[1..j]完全相等,故令j’=next[j]即可保证此性质保留KMP算法的运行过程•i=123456789……•A=abababaabab…•B=ababacbj=1234567•i=123456789……•A=abababaabab…•B=ababacbj‘=1234567KMP算法的运行过程•需要注意的是i并没有动，改变的只是j的值•如果改变j的值后a[i+1]仍不等于b[j+1]的话，继续改变j值直到a[i+1]==b[j+1]或者j=0•j=0表示i+1前面无论怎么匹配都不能使a[i+1]==b[j+1],只好让a[i+1]与b[j+1]单独匹配•还是上一个例子，再演示一下KMP算法的运行过程•i=123456789……•A=abababaabab…•B=ababacb•j=1234567•当i=6,j=5时，a[i+1]!=b[j+1],故令j=next[5]=3KMP算法的运行过程•i=123456789……•A=abababaabab…•B=ababacb•j=1234567•此时i=6,j=3仍不满足a[i+1]==b[j+1]，故继续减小j,使j=next[3]=1KMP算法的运行过程•i=123456789……•A=abababaabab…•B=ababacb•j=1234567•此时i=6,j=1仍不满足a[i+1]==b[j+1]，故继续减小j,使j=next[1]=0KMP算法的运行过程•i=123456789……•A=abababaabab…•B=ababacb•j=1234567•终于，A[8]=B[1]，i变为8，j为1KMP算法的运行过程•i=123456789……•A=abababadbab…•B=ababacb•j=1234567•事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]=“d”时）。因此，准确的说法是，当j=0了时，我们直接增加i值但忽略j直到出现A[i]=B[1]为止。KMP代码•//kmp•j=0;•for(i=0;ian;i++)•{•while(j0&&a[i]!=b[j])•j=next[j-1];•if(a[i]==b[j])•j++;•else•j=0;•}next数组•//next•memset(next,0,sizeof(next));•for(i=1;ibn;i++)•{•temp=next[i-1];•while(temp&&b[temp]!=b[i])•temp=next[temp-1];•if(b[temp]==b[i])•next[i]=temp+1;•else•next[i]=0;•}时间复杂度分析•由于while循环的不确定性，好像时间复杂度很高.•但事实上，我们可以看到无论是j还是temp，它只在程序的最后+1，故最多+n(+m)。因而while循环最多-n(-m),因而算法的复杂度都是线性的.•next的复杂度O(m),KMP的复杂度为O(n)关于next的一个性质•问题的提出:关于next的一个性质•现在的问题是：如何快速找出S的最小循环周期（循环节）呢？•Len是s的长度•给出结论：如果len%(len-next[len-1])==0,则字符串中必存在最小循环节，且循环次数即为len/(len-next[len-1])关于next的一个性质•证明：必要性：因为字符串中存在最小循环节(设长度为k)，next[len-1]=len-k,所以len%(len-next[len-1])==0;•充分性：令k1=len-next[len-1],由于k1整除len,所以可以相应的把len划分为n片区域(n=len/(k1))，从小到大依次表示为•t1,t2...tn;由next数组的定义可知，t1=t2,t2=t3,...t(n-1)=tn,且相应的片区域即为最小，所以循环次数也为len/(len-next[len-1]);关于next的一个性质•例：poj2406•题意：给你一串字符串，问它的循环次数•Sampleinput:•abcdaaaaababab•Sampleoutput•143核心代码如下•if(n%(n-next[n-1])==0)•printf(%d\n,n/(n-next[n-1]));•else•printf(1\n);关于next的一个性质•补充一下：•S:abcabcabca•n-next[n-1]=3,虽然10%3！=0，但是它有理论意义，可以看到若在S后面加上bc，abc就又是最小循环周期了。•故这里要注意的是len-next[len-1]为这个串的最小循环节的长度，这不需要最后的子串是完整的；if(len%(len–next[len-1])==0)这个求得的是串的最大的循环的个数这个要求最后的子串是完整的思考KMP不仅仅是匹配完全相等的情况，其思想完全适用于对一定规律的字符进行匹配Eg:=3167关于扩展KMP（了解）我们先比较一下KMP和扩展KMP所表示的意义KMP：next数组的性质是模式串中每一个位置的前缀和此串其实后缀的最大匹配个数kmp匹配时的性质是求出模板串在主串中出现的位置扩展KMP：next数组的性质是模板串中每一个位置的后缀和此串前缀匹配的最大个数kmp匹配的性质是主串中的每个位置和模板串的最多匹配个数。可以看到KMP匹配的是模式串的长度，显然扩展KMP是KMP的一种扩展扩展KMP像求KMP的next数组一样，我们先求A[i]，表示模式串的后缀和模式串的最长公共前缀,然后再利用A[i]求出B[i]说明一下A的求法，B同理现在我们要求A[i]，且A[1]---A[i-1]已经求出，设k，且1=k=i-1，并满足k+A[k]最大所以T[k]--T[k+A[k]-1]=T[0]--T[A[k]-1]，推出T[i]--T[k+A[k]-1]=T[i-k]--T[A[k]-1]令L=A[i-k]，若L+i-1k+A[k]-1，由A是最长公共前缀知A[i]=L，否则，向后匹配，直到字符串失配并相应更新扩展KMP关于复杂度：很容易看出，在计算的过程中，凡是访问过的点，都不需要重新访问了。一旦比较，都是比较以前从不曾探访过的点开始。因此总的时间复杂度是O(n+m),是线性的。扩展KMP//求模板串中的a数组j=0;while(T[0+j]==T[1+j])j=j+1;intA[1]=j,k=1;for(inti=2;im;i++){intLen=k+A[k]–1,L=A[i-k];if(LLen-i+1)A[i]=L;else{j=max(0,Len-i+1);while(T[i+j]==T[0+j])j=j+1;A[i]=j，k=i;}}扩展KMP//求主串中的b数组j=0;while(T[0+j]==S[0+j])j=j+1;intB[0]=j,k=0;for(inti=1;im;i++){intLen=k+B[k]-1,L=A[i-k];if(LLen-i+1)B[i]=L;else{j=max(0,Len-i+1);while(S[i+j]==T[0+j])j=j+1;B[i]=j，k=i;}}Hdu3336字符串问题•Trie树•AC自动机•后缀树组•hash作业•Poj2752•Poj2406•Hdu1711•Poj1961•Poj3461•Fzu1901•Poj2185•Hdu1867•Hdu3336•较难：poj3167