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

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

1、4.3.2KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,簡稱KMP算法。該算法較BF算法有較大改進(jìn),主要是消除了主串指針的回溯,從而使算法效率有了某種程度的提高。所謂真子串是指模式串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)以下

2、情況：這時，應(yīng)有"t0t1…tj-1"="si-jsi-j+1…si-1"(4.1)如果在模式t中，"t0t1…tj-1"≠"t1t2…tj"(4.2)則回溯到si-j+1開始與t匹配，必然“失配”，理由很簡單：由(4.1)式和(4.2)式綜合可知："t0t1…tj-1"≠"si-j+1si-j+2…si"既然如此，回溯到si-j+1開始與t匹配可以不做。那么，回溯到si-j+2開始與t匹配又怎么樣？從上面推理可知，如果"t0t1…tj-2"≠"t2t3…tj"仍然有"t0t1…tj-2"≠"si-j+2si-j+3…si"這樣的比較仍然“失配”

3、。依此類推，直到對于某一個值k，使得："t0t1…tk-2"≠"tj-k+1tj-k+2…tj-1"且"t0t1…tk-1"="tj-ktj-k+1…tj-1“才有"tj-ktj-k+1…tj-1"="si-ksi-k+1…si-1"="t0t1…tk-1"說明下一次可直接比較si和tk，這樣，我們可以直接把第i趟比較“失配”時的模式t從當(dāng)前位置直接右滑j-k位。而這里的k即為next[j]。例如t="abab",由于"t0t1"="t2t3"(這里k=1,j=3),則存在真子串。設(shè)s="abacabab",t="abab",第一次匹配過程如下所

4、示。此時不必從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

5、0

6、0;k=-1;next[0]=-1;while(j

7、

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

9、

10、s.data[i]==t.data[j]){i++;j++;}/

11、*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)前比

12、較字符位置,用指針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等三次比較。實際上,因為模式中的第1、2、3個字符和第4個字符都相等,因此,不需要再和主串中第4個字符相比較,而可以將模式一次向右滑動4個字符的位置直接進(jìn)行i=4,j=0時的

13、字符比較。這就是說,若按上述定義得到next[j]=k,而模式中pj=pk,則為主串中字符si和pj比較不等時,不需要再和pk進(jìn)行比較,