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

1、严蔚敏-数据结构-kmp算法详解 4.3.2 KMP 4.3.2 KMP算法算法 KMP算法是、和共同提出的算法是、和共同提出的,简称简称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+2tj-1 且且 t0t1

4、tk-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 si-k si-k+1

5、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,又因又因t0 =t2,s2=

6、t2,所以必有所以必有s2=t0。因此。因此,第二次匹配可直接从第二次匹配可直接从i=3,j=1开始。开始。 为此为此,定义定义nextj函数如下函数如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j0123tjababnextj-1001t=“abab”t=“abab”对应的对应的nextnext数组如下数组如下:void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.len-1) i

7、f (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 & j=) v=; /*返回匹配模式串的首字符下标返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志返回不匹配标志*/ return v; KMP算法算法 设主串设主串s的

8、长度为的长度为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的当前比较字符位置。的当前比较

9、字符位置。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=aaabaaaab i=9 t=aaaab j=5,返回返回 10-

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个字符都相等个字符都相等,因此因此,不需要再和主串中第不需要再和主串中第4个个字符相比较字符相比较,而可以将模式一次向右滑动而可以将模

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

12、xtvalk;void GetNextval(SqString t,int nextval) int j=0,k=-1; nextval0=-1; while (j) 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 & j=) v=; /*返回匹配模式串的首字符下标返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配