最新嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu)-kmp算法詳解教學(xué)講義ppt.ppt

《最新嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu)-kmp算法詳解教學(xué)講義ppt.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu)-kmp算法詳解所謂真子串是指模式串t存在某個k(0＜k＜j)，使得"t0t1…tk"="tj-ktj-k+1…tj"成立。例如，t="abab",即t0t1＝t2t3也就是說，“ab”是真子串。真子串就是模式串中隱藏的信息，利用它來提高模式匹配的效率。一般情況:設(shè)主串s="s0s1…sn-1",模式t="t0t1…tm-1",在進(jìn)行第i趟匹配時，出現(xiàn)以下情況：這時，應(yīng)有"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),則存在真子串。設(shè)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]函數(shù)如下: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;/*返回匹配模式串的首字符下標(biāo)*/elsev=-1;/*返回不匹配標(biāo)志*/returnv;}KMP算法設(shè)主串s的長度為n,子串t長度為m。在KMP算法中求next數(shù)組的時間復(fù)雜度為O(m),在后面的匹配中因主串s的下標(biāo)不減即不回溯,比較次數(shù)可記為n,所以KMP算法總的時間復(fù)雜度為O(n+m)。例如,設(shè)目標(biāo)串s=“aaabaaaab”,模式串t=“aaaab”。s的長度為n(n=9),t的長度為m(m=5)。用指針i指示目標(biāo)串s的當(dāng)前

10、比較字符位置,用指針j指示模式串t的當(dāng)前比較字符位置。KMP模式匹配過程如下所示。j01234t[j]aaaabnext[j]-10123上述定義的next[]在某些情況下尚有缺陷。例如,模式“aaaab”在和主串“aaabaaaab”匹配時,當(dāng)i=3,j=3時,s.data[3]≠t.data[3],由next[j]的指示還需進(jìn)行i=3、j=2,i=3、j=1,i=3、j=0等三次比較。實(shí)際上,因?yàn)槟Ｊ街械牡?、2、3個字符和第4個字符都相等,因此,不需要再和主串中第4個字符相比較,而可以將模式一次向右滑動4個字符的位置直接進(jìn)行i=4,j=0時的字符比較。這就是說,若按上述定

11、義得到next[j]=k,而模式中pj=pk,則為主串中字符si和pj比較不等時,不需要再和pk進(jìn)行比較,而直接和pnext[k]進(jìn)行比較,換句話說,此時的next[j]應(yīng)和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]=