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

《严蔚敏数据结构kmp算法详解.ppt》由会员分享，可在线阅读，更多相关《严蔚敏数据结构kmp算法详解.ppt（18页珍藏版）》请在优知文库上搜索。

1、 4.3.2 KMP 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”是真子串。是真子串。 真子

2、串就是模式串中隐藏的信息，利用它来提高真子串就是模式串中隐藏的信息，利用它来提高模式匹配的效率。模式匹配的效率。 一般情况一般情况:设主串设主串s=s0s1sn-1,模式模式t=t0t1tm-1,在进行第在进行第i趟匹配时，出现以下情况：趟匹配时，出现以下情况：这时，应有这时，应有t0t1tj-1=si-jsi-j+1si-1 (4.1)如果在模式如果在模式t中，中，t0t1tj-1t1t2tj (4.2) s： s0 s1 si-j si-j+1 si-1 si si+1 sn-1 t： t0 t1 tj-1 tj tj+1 sm-1 则回溯到则回溯到si-j+1开始与开始与t匹配，必然匹配

3、，必然“失配失配”，理由，理由很简单：由很简单：由(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+2

4、tj-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。 s： s0 s1 si-j si-j+1 si-k si-k+1 si-1 si si+1 sn-1 t： t0 t1 tk-1 tk tj-1 tj tj+1 sm-1 s： s0 s1 si-j si-j+1

5、si-k si-k+1 si-1 si si+1 sn-1 t： t0 t1 tk-1 tk tj-1 tj tj+1 sm-1 t 右滑右滑 j-k 位位 例如例如t=abab,由于由于t0t1 =t2t3(这里这里k=1,j=3),则则存在真子串。设存在真子串。设s=abacabab,t=abab,第一次匹第一次匹配过程如下所示。配过程如下所示。 第第 1 次匹配次匹配 s=a b a c a b a b i=3 t=a b a b j=3 失败 此时不必从此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹重新开始第二次匹配。因配。因t0t1,s1=t1,必有必有s1t0,又因

6、又因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=j0123tjababnextj-1001t=“ababt=“abab”对应的对应的nextnext数组如下数组如下:void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (

7、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 (is.len & j=t.len) v=i-t.len; /*返回匹配模式串的首字符下标返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志返回不匹配

8、标志*/ 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的当前比较字符位置的当前比较字符位置,用指

9、针用指针j指示模式串指示模式串t的当的当前比较字符位置。前比较字符位置。KMP模式匹配过程如下所示。模式匹配过程如下所示。 第第 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=next3=2 失败失败 第第 2 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=2,j=next2=1 失败失败 第第 3 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=1,j=next1=0 失败失败 第第 4 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=0,j=next0=-1 失败失败 第第 5 次匹配次匹配 s=aaa

10、baaaab i=9 t=aaaab j=5,返回返回 10-5=4 成功成功 j01234tjaaaabnextj-10123 上述定义的上述定义的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个字符都相等个字符都相等,因因此此,不需要再和主串中第不需要再和主串中第

11、4个字符相比较个字符相比较,而可以将模式而可以将模式一次向右滑动一次向右滑动4个字符的位置直接进行个字符的位置直接进行i=4,j=0时的字时的字符比较。符比较。 这就是说这就是说,若按上述定义得到若按上述定义得到nextj=k,而模式中而模式中pj=pk,则为主串中字符则为主串中字符si和和pj比较不等时比较不等时,不需要再和不需要再和pk进行比较进行比较,而直接和而直接和pnextk进行比较进行比较,换句话说换句话说,此时的此时的nextj应和应和nextk相同。相同。 为此将为此将nextj修正为修正为nextvalj： 比较比较t.dataj和和t.datak，若不等，则，若不等，则 n

12、extvalj=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+; i f ( t . d a t a j ! = t . d a t a k ) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; 由模式串由模式串t求求出出nextval值值int KMPIndex1(SqString s,SqStr

13、ing t) int nextvalMaxSize,i=0,j=0,v; GetNextval(t,nextval); while (is.len & j=t.len) v=i-t.len; /*返回匹配模式串的首字符下标返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志返回不匹配标志*/ return v; 修改后的修改后的KMP算法算法j01234tjaaaabnextj-10123nextvalj-1-1-1-13 第第 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=nextval3=-1 失败失败 第第 2 次匹配次匹配 s=aaabaaaab i=9 t=aaaab j=5,返回返回 9-5=4 成功成功