严蔚敏数据结构kmp算法详解完整版

1、 所谓所谓真子串真子串是指模式串是指模式串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

2、) 如果在模式如果在模式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匹配，必然匹配，必然“失配失配”，理由，理由 很简单：由很简单：由(4.1)式和式和(4.2)式综合可知：式综合可知： t0t1tj-1si-j+1si-j+2si 既然如此，回溯到既然如此，回溯到si-j+1开始与开始与t匹配可以不做。那匹配可以不做。那 么，回溯到么，回溯到si-j+2开始与开始与t匹配又怎么样？从上面推理匹配又怎么样？从上面

3、推理 可知，如果可知，如果 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从当前位置直从当前位置

4、直 接右滑接右滑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 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,第一次匹第

5、一次匹 配过程如下所示。配过程如下所示。 第第 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=t2,所以必有所以必有 s2=t0。因此。因此,第二次匹配可直接从第二次匹配可直接从i=3,j=1开始。开始。 为此为此,定义定义nextj函数如下函数如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时

6、时 0 其他情况其他情况 nextj= j0123 tjabab nextj-1001 t=“abab”t=“abab”对应的对应的nextnext数组如下数组如下: 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(SqS

7、tring s,SqString t) int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (is.len /*返回匹配模式串的首字符下标返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志返回不匹配标志*/ return v; KMP算法算法 设主串设主串s的长度为的长度为n,子串子串t长度为长度为m。 在在KMP算法中求算法中求next数组的时间复杂度为数组的时间复杂度为 O(m),在后面的匹配中因主串在后面的匹配中因主串s的下标不减即不回溯的下标不减即不回溯, 比较次数可记为比较次数可记为n,所以所以KMP算法总的时间复

8、杂度为算法总的时间复杂度为 O(n+m)。 例如例如,设目标串设目标串s=“aaabaaaab”,模式串模式串t=“aaaab”。 s的长度为的长度为n(n=9),t的长度为的长度为m(m=5)。用指针。用指针i指示目指示目 标串标串s的当前比较字符位置的当前比较字符位置,用指针用指针j指示模式串指示模式串t的当的当 前比较字符位置。前比较字符位置。KMP模式匹配过程如下所示。模式匹配过程如下所示。 第第 1 次匹配次匹配 s=aaabaaaa b i=3 t=aaaab j=3,j=next3=2 失败失败 第第 2 次匹配次匹配 s=aaabaaaa b i=3 t=aaaab j=2,j

9、=next2=1 失败失败 第第 3 次匹配次匹配 s=aaabaaaa b i=3 t=aaaab j=1,j=next1=0 失败失败 第第 4 次匹配次匹配 s=aaabaaaa b i=3 t=aaaab j=0,j=next0=-1 失败失败 第第 5 次匹配次匹配 s=aaabaaaa b i=9 t=aaaab j=5,返回返回 10-5=4 成功成功 j01234 tjaaaab nextj-10123 上述定义的上述定义的next在某些情况下尚有缺陷。在某些情况下尚有缺陷。 例如例如,模式模式“aaaab”在和主串在和主串“aaabaaaab”匹配时匹配时, 当当i=3,j=

10、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和和

11、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+; 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,SqString t) int nextvalMaxSize,i=0,j=0,v; GetNextval(t,nextval); while (is.len /*返回匹配模式串的首字符下标返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志返回不匹配标志*/