《严蔚敏-数据结构-kmp算法详解》由会员分享，可在线阅读，更多相关《严蔚敏-数据结构-kmp算法详解（18页珍藏版）》请在金锄头文库上搜索。
1、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趟匹配时，出现以下情况： 这时，应有 “t0t1t
2、j-1“=“si-jsi-j+1si-1“ (4.1) 如果在模式t中， “t0t1tj-1“t1t2tj“ (4.2),则回溯到si-j+1开始与t匹配，必然“失配”，理由很简单：由(4.1)式和(4.2)式综合可知： “t0t1tj-1“si-j+1si-j+2si“ 既然如此，回溯到si-j+1开始与t匹配可以不做。那么，回溯到si-j+2开始与t匹配又怎么样？从上面推理可知，如果 “t0t1tj-2“t2t3tj“ 仍然有 “t0t1tj-2“si-j+2si-j+3si“,这样的比较仍然“失配”。依此类推，直到对于某一个值k，使得： “t0t1tk-2“ tj-k+1tj-k+2tj
3、-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,所
4、以必有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求
5、出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=“
6、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时的字符比较。,这就是说,若按上
7、述定义得到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算法,
