严蔚敏数据结构kmp算法详解.ppt
4.3.2 KMP算法 KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。,所谓真子串是指模式串t存在某个k(0kj)，使得t0t1tk=tj-ktj-k+1tj 成立。例如，t=abab,即t0t1t2t3 也就是说，“ab”是真子串。真子串就是模式串中隐藏的信息，利用它来提高模式匹配的效率。,一般情况:设主串s=s0s1sn-1,模式t=t0t1tm-1,在进行第i趟匹配时，出现以下情况：这时，应有t0t1tj-1=si-jsi-j+1si-1(4.1)如果在模式t中，t0t1tj-1t1t2tj(4.2),则回溯到si-j+1开始与t匹配，必然“失配”，理由很简单：由(4.1)式和(4.2)式综合可知：t0t1tj-1si-j+1si-j+2si 既然如此，回溯到si-j+1开始与t匹配可以不做。那么，回溯到si-j+2开始与t匹配又怎么样？从上面推理可知，如果 t0t1tj-2t2t3tj仍然有 t0t1tj-2si-j+2si-j+3si,这样的比较仍然“失配”。依此类推，直到对于某一个值k，使得：t0t1tk-2 tj-k+1tj-k+2tj-1 且 t0t1tk-1=tj-ktj-k+1tj-1“才有 tj-ktj-k+1tj-1=si-ksi-k+1si-1=t0t1tk-1,说明下一次可直接比较si和tk，这样，我们可以直接把第i趟比较“失配”时的模式t从当前位置直接右滑j-k位。而这里的k即为nextj。,例如t=abab,由于t0t1=t2t3(这里k=1,j=3),则存在真子串。设s=abacabab,t=abab,第一次匹配过程如下所示。,此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹配。因t0t1,s1=t1,必有s1t0,又因t0=t2,s2=t2,所以必有s2=t0。因此,第二次匹配可直接从i=3,j=1开始。,为此,定义nextj函数如下:maxk|0kj,且“t0t1tk-1”=“tj-ktj-k+1tj-1”当此集合非空时-1 当j=0时 0 其他情况,nextj=,t=“abab”对应的next数组如下:,void GetNext(SqString t,int next)int j,k;j=0;k=-1;next0=-1;while(jt.len-1)if(k=-1|t.dataj=t.datak)/*k为-1或比较的字符相等时*/j+;k+;nextj=k;else k=nextk;,由模式串t求出next值的算法,int KMPIndex(SqString s,SqString t)int nextMaxSize,i=0,j=0,v;GetNext(t,next);while(i=t.len)v=i-t.len;/*返回匹配模式串的首字符下标*/else v=-1;/*返回不匹配标志*/return v;,KMP算法,设主串s的长度为n,子串t长度为m。在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(n+m)。,例如,设目标串s=“aaabaaaab”,模式串t=“aaaab”。s的长度为n(n=9),t的长度为m(m=5)。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置。KMP模式匹配过程如下所示。,上述定义的next在某些情况下尚有缺陷。例如,模式“aaaab”在和主串“aaabaaaab”匹配时,当i=3,j=3时,s.data3t.data3,由nextj的指示还需进行i=3、j=2,i=3、j=1,i=3、j=0等三次比较。实际上,因为模式中的第1、2、3个字符和第4个字符都相等,因此,不需要再和主串中第4个字符相比较,而可以将模式一次向右滑动4个字符的位置直接进行i=4,j=0时的字符比较。,这就是说,若按上述定义得到nextj=k,而模式中pj=pk,则为主串中字符si和pj比较不等时,不需要再和pk进行比较,而直接和pnextk进行比较,换句话说,此时的nextj应和nextk相同。为此将nextj修正为nextvalj：比较t.dataj和t.datak，若不等，则 nextvalj=nextj;若相等nextvalj=nextvalk;,void GetNextval(SqString t,int nextval)int j=0,k=-1;nextval0=-1;while(jt.len)if(k=-1|t.dataj=t.datak)j+;k+;if(t.dataj!=t.datak)nextvalj=k;else nextvalj=nextvalk;else k=nextvalk;,由模式串t求出nextval值,int KMPIndex1(SqString s,SqString t)int nextvalMaxSize,i=0,j=0,v;GetNextval(t,nextval);while(i=t.len)v=i-t.len;/*返回匹配模式串的首字符下标*/else v=-1;/*返回不匹配标志*/return v;,修改后的KMP算法,
