最新严蔚敏-数据结构-kmp算法详解教学讲义ppt.ppt

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

1、严蔚敏-数据结构-kmp算法详解所谓真子串是指模式串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趟匹配时，出现以下情况：这时，应有"t0t1…tj-1"="si-jsi-j+1…si-1"(4.1)如果在模式t中，"t0t1…tj-1"≠"t1t2…tj"(4.2)例如t="abab",由于"t0t1"="t2t3"(这里

2、k=1,j=3),则存在真子串。设s="abacabab",t="abab",第一次匹配过程如下所示。此时不必从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

3、0

4、xt(SqStringt,intnext[]){intj,k;j=0;k=-1;next[0]=-1;while(j

5、

6、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

7、

8、s.data[i]==t.da

9、ta[j]){i++;j++;}/*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的当前

10、比较字符位置,用指针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时的字符比较。这就是说,若按上述定

11、义得到next[j]=k,而模式中pj=pk,则为主串中字符si和pj比较不等时,不需要再和pk进行比较,而直接和pnext[k]进行比较,换句话说,此时的next[j]应和next[k]相同。为此将next[j]修正为nextval[j]：比较t.data[j]和t.data[k]，若不等，则nextval[j]=next[j];若相等nextval[j]=nextval[k];voidGetNextval(SqStringt,intnextval[]){intj=0,k=-1;nextval[0]=-1;while(j

12、

13、t.data[j]=

14、=t.data[k]){j++;k++;if(t.data[j]!=t.data[k])nextval[j]=k;elsenextval[j]=nextval[k];}elsek=nextval[k];}}由模式串t求出nextval值intKMPIndex1(SqStrings,SqStringt){intnextval[MaxSize],i=0,j=0,v;GetNextval(t,nextval);while(i

15、

16、s.data[i]=