严蔚敏-数据结构-kmp算法详解.ppt

《严蔚敏-数据结构-kmp算法详解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.3.2KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。所谓真子串是指模式串t存在某个k(0＜k＜j)，使得"t0t1…tk"="tj-ktj-k+1…tj"成立。例如，t="abab",即t0t1＝t2t3也就是说，“ab”是真子串。真子串就是模式串中隐藏的信息，利用它来提高模式匹配的效率。一般情况:设主串s="s0s1…sn-1",模式t="t0t1…tm-1",在进行第i趟匹配时，出现以下

2、情况：这时，应有"t0t1…tj-1"="si-jsi-j+1…si-1"(4.1)如果在模式t中，"t0t1…tj-1"≠"t1t2…tj"(4.2)则回溯到si-j+1开始与t匹配，必然“失配”，理由很简单：由(4.1)式和(4.2)式综合可知："t0t1…tj-1"≠"si-j+1si-j+2…si"既然如此，回溯到si-j+1开始与t匹配可以不做。那么，回溯到si-j+2开始与t匹配又怎么样？从上面推理可知，如果"t0t1…tj-2"≠"t2t3…tj"仍然有"t0t1…tj-2"≠"si-j+2si-j+3…si"这样的比较仍然“失配”

3、。依此类推，直到对于某一个值k，使得："t0t1…tk-2"≠"tj-k+1tj-k+2…tj-1"且"t0t1…tk-1"="tj-ktj-k+1…tj-1“才有"tj-ktj-k+1…tj-1"="si-ksi-k+1…si-1"="t0t1…tk-1"说明下一次可直接比较si和tk，这样，我们可以直接把第i趟比较“失配”时的模式t从当前位置直接右滑j-k位。而这里的k即为next[j]。例如t="abab",由于"t0t1"="t2t3"(这里k=1,j=3),则存在真子串。设s="abacabab",t="abab",第一次匹配过程如下所

4、示。此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹配。因t0≠t1,s1=t1,必有s1≠t0,又因t0=t2,s2=t2,所以必有s2=t0。因此,第二次匹配可直接从i=3,j=1开始。为此,定义next[j]函数如下:max{k

5、0

6、0;k=-1;next[0]=-1;while(j

7、

8、t.data[j]==t.data[k])/*k为-1或比较的字符相等时*/{j++;k++;next[j]=k;}elsek=next[k];}}由模式串t求出next值的算法intKMPIndex(SqStrings,SqStringt){intnext[MaxSize],i=0,j=0,v;GetNext(t,next);while(i

9、

10、s.data[i]==t.data[j]){i++;j++;}/

11、*i,j各增1*/elsej=next[j];/*i不变,j后退*/}if(j>=t.len)v=i-t.len;/*返回匹配模式串的首字符下标*/elsev=-1;/*返回不匹配标志*/returnv;}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的当前比

12、较字符位置,用指针j指示模式串t的当前比较字符位置。KMP模式匹配过程如下所示。j01234t[j]aaaabnext[j]-10123上述定义的next[]在某些情况下尚有缺陷。例如,模式“aaaab”在和主串“aaabaaaab”匹配时,当i=3,j=3时,s.data[3]≠t.data[3],由next[j]的指示还需进行i=3、j=2,i=3、j=1,i=3、j=0等三次比较。实际上,因为模式中的第1、2、3个字符和第4个字符都相等,因此,不需要再和主串中第4个字符相比较,而可以将模式一次向右滑动4个字符的位置直接进行i=4,j=0时的

13、字符比较。这就是说,若按上述定义得到next[j]=k,而模式中pj=pk,则为主串中字符si和pj比较不等时,不需要再和pk进行比较,