【優(yōu)品課件】——《kmp算法詳解》

《【優(yōu)品課件】——《kmp算法詳解》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、KMP算法詳解假如，A="abababaababacb"，B="ababacb"，我們來(lái)看看KMP是怎么工作的。我們用兩個(gè)指針i和j分別表示，A[i-j+1..i]與B[1..j]完全相等。也就是說(shuō)，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以A[i]結(jié)尾的長(zhǎng)度為j的字符串正好匹配B串的前j個(gè)字符（j當(dāng)然越大越好），現(xiàn)在需要檢驗(yàn)A[i+1]和B[j+1]的關(guān)系。當(dāng)A[i+1]=B[j+1]時(shí)，i和j各加一；什么時(shí)候j=m了，我們就說(shuō)B是A的子串（B串已經(jīng)整完了），并且可以根據(jù)這時(shí)的i值算出匹配的位置。當(dāng)A[i+1]<>B[j+1]，KMP的策略是調(diào)整j的位置（減小j

2、值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續(xù)增加）。我們看一看當(dāng)i=j=5時(shí)的情況。i=123456789??A=abababaabab?B=ababacbj=1234567此時(shí)，A[6]<>B[6]。這表明，此時(shí)j不能等于5了，我們要把j改成比它小的值j'。j'可能是多少呢？仔細(xì)想一下，我們發(fā)現(xiàn)，j'必須要使得B[1..j]中的頭j'個(gè)字母和末j'個(gè)字母完全相等（這樣j變成了j'后才能繼續(xù)保持i和j的性質(zhì)）。這個(gè)j'當(dāng)然要越大越好。在這里，B[1..5]="ababa"，頭3個(gè)字母和末3個(gè)字母都是"a

3、ba"。而當(dāng)新的j為3時(shí)，A[6]恰好和B[4]相等。于是，i變成了6，而j則變成了4：i=123456789??A=abababaabab?B=ababacbj=1234567從上面的這個(gè)例子，我們可以看到，新的j可以取多少與i無(wú)關(guān)，只與B串有關(guān)。我們完全可以預(yù)處理出這樣一個(gè)數(shù)組P[j]，表示當(dāng)匹配到B數(shù)組的第j個(gè)字母而第j+1個(gè)字母不能匹配了時(shí)，新的j最大是多少。P[j]應(yīng)該是所有滿足B[1..P[j]]=B[j-P[j]+1..j]的最大值。再后來(lái)，A[7]=B[5]，i和j又各增加1。這時(shí)，又出現(xiàn)了A[i+1]<>B[j+1]的情況：i=123456789??A=a

4、bababaabab?B=ababacbj=1234567由于P[5]=3，因此新的j=3：i=123456789??A=abababaabab?B=ababacbj=1234567這時(shí)，新的j=3仍然不能滿足A[i+1]=B[j+1]，此時(shí)我們?cè)俅螠p小j值，將j再次更新為P[3]：i=123456789??A=abababaabab?B=ababacbj=1234567現(xiàn)在，i還是7，j已經(jīng)變成1了。而此時(shí)A[8]居然仍然不等于B[j+1]。這樣，j必須減小到P[1]，即0：i=123456789??A=abababaabab?B=ababacbj=01234567終于，

5、A[8]=B[1]，i變?yōu)?，j為1。事實(shí)上，有可能j到了0仍然不能滿足A[i+1]=B[j+1]（比如A[8]="d"時(shí)）。因此，準(zhǔn)確的說(shuō)法是，當(dāng)j=0了時(shí)，我們?cè)黾觟值但忽略j直到出現(xiàn)A[i]=B[1]為止。這個(gè)過(guò)程的代碼很短（真的很短），我們?cè)谶@里給出：1j:=0;fori:=1tondobeginwhile(j>0)and(B[j+1]<>A[i])doj:=P[j];ifB[j+1]=A[i]thenj:=j+1;ifj=mthenbeginwriteln('Patternoccurswithshift',i-m);j:=P[j];end;end;最后的j:=P[

6、j]是為了讓程序繼續(xù)做下去，因?yàn)槲覀冇锌赡苷业蕉嗵幤ヅ?。這個(gè)程序或許比想像中的要簡(jiǎn)單，因?yàn)閷?duì)于i值的不斷增加，代碼用的是for循環(huán)。因此，這個(gè)代碼可以這樣形象地理解：掃描字符串A，并更新可以匹配到B的什么位置?，F(xiàn)在，我們還遺留了兩個(gè)重要的問(wèn)題：一，為什么這個(gè)程序是線性的；二，如何快速預(yù)處理P數(shù)組。為什么這個(gè)程序是O(n)的？其實(shí)，主要的爭(zhēng)議在于，while循環(huán)使得執(zhí)行次數(shù)出現(xiàn)了不確定因素。我們將用到時(shí)間復(fù)雜度的攤還分析中的主要策略，簡(jiǎn)單地說(shuō)就是通過(guò)觀察某一個(gè)變量或函數(shù)值的變化來(lái)對(duì)零散的、雜亂的、不規(guī)則的執(zhí)行次數(shù)進(jìn)行累計(jì)。KMP的時(shí)間復(fù)雜度分析可謂攤還分析的典型。我們從上述程

7、序的j值入手。每一次執(zhí)行while循環(huán)都會(huì)使j減?。ǖ荒軠p成負(fù)的），而另外的改變j值的地方只有第五行。每次執(zhí)行了這一行，j都只能加1；因此，整個(gè)過(guò)程中j最多加了n個(gè)1。于是，j最多只有n次減小的機(jī)會(huì)（j值減小的次數(shù)當(dāng)然不能超過(guò)n，因?yàn)閖永遠(yuǎn)是非負(fù)整數(shù)）。這告訴我們，while循環(huán)總共最多執(zhí)行了n次。按照攤還分析的說(shuō)法，平攤到每次for循環(huán)中后，一次for循環(huán)的復(fù)雜度為O(1)。整個(gè)過(guò)程顯然是O(n)的。這樣的分析對(duì)于后面P數(shù)組預(yù)處理的過(guò)程同樣有效，同樣可以得到預(yù)處理過(guò)程的復(fù)雜度為O(m)。預(yù)處理不需要按照P的定義