kmp小記-創(chuàng)新互聯(lián)

以下轉(zhuǎn)載自Matrix67

*****************************************************************************************************************************

創(chuàng)新互聯(lián)長(zhǎng)期為上千多家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為羅平企業(yè)提供專(zhuān)業(yè)的成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)，羅平網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。

如果機(jī)房馬上要關(guān)門(mén)了，或者你急著要和MM約會(huì)，請(qǐng)直接跳到第六個(gè)自然段。

    我們這里說(shuō)的KMP不是拿來(lái)放電影的（雖然我很喜歡這個(gè)軟件），而是一種算法。KMP算法是拿來(lái)處理字符串匹配的。換句話說(shuō)，給你兩個(gè)字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我們就說(shuō)B是A的子串。你可以委婉地問(wèn)你的MM：“假如你要向你喜歡的人表白的話，我的名字是你的告白語(yǔ)中的子串嗎？”
    解決這類(lèi)問(wèn)題，通常我們的方法是枚舉從A串的什么位置起開(kāi)始與B匹配，然后驗(yàn)證是否匹配。假如A串長(zhǎng)度為n，B串長(zhǎng)度為m，那么這種方法的復(fù)雜度是O (mn)的。雖然很多時(shí)候復(fù)雜度達(dá)不到mn（驗(yàn)證時(shí)只看頭一兩個(gè)字母就發(fā)現(xiàn)不匹配了），但我們有許多“最壞情況”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我們將介紹的是一種最壞情況下O(n)的算法（這里假設(shè) m<=n），即傳說(shuō)中的KMP算法。
    之所以叫做KMP，是因?yàn)檫@個(gè)算法是由Knuth、Morris、Pratt三個(gè)提出來(lái)的，取了這三個(gè)人的名字的頭一個(gè)字母。這時(shí)，或許你突然明白了AVL 樹(shù)為什么叫AVL，或者Bellman-Ford為什么中間是一杠不是一個(gè)點(diǎn)。有時(shí)一個(gè)東西有七八個(gè)人研究過(guò)，那怎么命名呢？通常這個(gè)東西干脆就不用人名字命名了，免得發(fā)生爭(zhēng)議，比如“3x+1問(wèn)題”。扯遠(yuǎn)了。
    個(gè)人認(rèn)為KMP是最沒(méi)有必要講的東西，因?yàn)檫@個(gè)東西網(wǎng)上能找到很多資料。但網(wǎng)上的講法基本上都涉及到“移動(dòng)(shift)”、“Next函數(shù)”等概念，這非常容易產(chǎn)生誤解（至少一年半前我看這些資料學(xué)習(xí)KMP時(shí)就沒(méi)搞清楚）。在這里，我換一種方法來(lái)解釋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值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續(xù)增加）。我們看一看當(dāng) i=j=5時(shí)的情況。

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B = a b a b a c b
    j = 1 2 3 4 5 6 7

    此時(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è)字母都是"aba"。而當(dāng)新的j為3時(shí)，A[6]恰好和B[4]相等。于是，i變成了6，而j則變成了 4：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =    a b a b a c b
    j =    1 2 3 4 5 6 7

    從上面的這個(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 = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =    a b a b a c b
    j =    1 2 3 4 5 6 7

    由于P[5]=3，因此新的j=3：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =        a b a b a c b
    j =        1 2 3 4 5 6 7

    這時(shí)，新的j=3仍然不能滿足A[i+1]=B[j+1]，此時(shí)我們?cè)俅螠p小j值，將j再次更新為P[3]：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =             a b a b a c b
    j =             1 2 3 4 5 6 7

    現(xiàn)在，i還是7，j已經(jīng)變成1了。而此時(shí)A[8]居然仍然不等于B[j+1]。這樣，j必須減小到P[1]，即0：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =              a b a b a c b
    j =             0 1 2 3 4 5 6 7

    終于，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è)谶@里給出：

j:=0;
for i:=1 to n do
begin
  while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
  if B[j+1]=A[i] then j:=j+1;
  if j=m then
  begin
      writeln('Pattern occurs with shift ',i-m);
      j:=P[j];
  end;
end;

    最后的j:=P[j]是為了讓程序繼續(xù)做下去，因?yàn)槲覀冇锌赡苷业蕉嗵幤ヅ洹?br />    這個(gè)程序或許比想像中的要簡(jiǎn)單，因?yàn)閷?duì)于i值的不斷增加，代碼用的是for循環(huán)。因此，這個(gè)代碼可以這樣形象地理解：掃描字符串A，并更新可以匹配到B的什么位置。

    現(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ù)雜度分析可謂攤還分析的典型。我們從上述程序的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的定義寫(xiě)成O(m^2)甚至O(m^3)的。我們可以通過(guò)P[1],P[2],...,P[j-1]的值來(lái)獲得P[j]的值。對(duì)于剛才的B="ababacb"，假如我們已經(jīng)求出了P[1],P[2],P[3]和P[4]，看看我們應(yīng)該怎么求出P[5]和P[6]。P[4]=2，那么P [5]顯然等于P[4]+1，因?yàn)橛蒔[4]可以知道，B[1,2]已經(jīng)和B[3,4]相等了，現(xiàn)在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一個(gè)字符得到。P[6]也等于P[5]+1嗎？顯然不是，因?yàn)锽[ P[5]+1 ]<>B[6]。那么，我們要考慮“退一步”了。我們考慮P[6]是否有可能由P[5]的情況所包含的子串得到，即是否P[6]=P[ P[5] ]+1。這里想不通的話可以仔細(xì)看一下：

        1 2 3 4 5 6 7
    B = a b a b a c b
    P = 0 0 1 2 3 ?

    P[5]=3是因?yàn)锽[1..3]和B[3..5]都是"aba"；而P[3]=1則告訴我們，B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5]得到，或許可以由P[3]得到（如果B[2]恰好和B[6]相等的話，P[6]就等于P[3]+1了）。顯然，P[6]也不能通過(guò)P[3]得到，因?yàn)锽[2]<>B[6]。事實(shí)上，這樣一直推到P[1]也不行，最后，我們得到，P[6]=0。
    怎么這個(gè)預(yù)處理過(guò)程跟前面的KMP主程序這么像呢？其實(shí)，KMP的預(yù)處理本身就是一個(gè)B串“自我匹配”的過(guò)程。它的代碼和上面的代碼神似：

P[1]:=0;
j:=0;
for i:=2 to m do
begin
  while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
  if B[j+1]=B[i] then j:=j+1;
  P[i]:=j;
end;

    最后補(bǔ)充一點(diǎn)：由于KMP算法只預(yù)處理B串，因此這種算法很適合這樣的問(wèn)題：給定一個(gè)B串和一群不同的A串，問(wèn)B是哪些A串的子串。

    串匹配是一個(gè)很有研究?jī)r(jià)值的問(wèn)題。事實(shí)上，我們還有后綴樹(shù)，自動(dòng)機(jī)等很多方法，這些算法都巧妙地運(yùn)用了預(yù)處理，從而可以在線性的時(shí)間里解決字符串的匹配。我們以后來(lái)說(shuō)。

***************************************************************************************************************************

第一：對(duì)于B串處理，p數(shù)組記錄的是什么？

~~~p[i]的值記錄的是i字符之前最長(zhǎng)有多長(zhǎng)與B字符串的開(kāi)頭的字符相同

第二：為什么該求p數(shù)組時(shí)，j = p[j]?

~~~~:

 看一下這組例子：

a b a b a c b a b a b a b a b b a b a c a b c
0 0 1 2 3 0 0 1 2 3 4 5 4 5 4 0 1 2 3 0 1 2 0

我們以第13個(gè)字符'b'為例：

  當(dāng)前p[12] = 5，但是 B[6] 卻不等于B[13],所以要回找j。。

  但是j往前找多少好呢？

  由定義，我們發(fā)現(xiàn)現(xiàn)在B[8-12]完全可以當(dāng)成B[1-5]來(lái)看，所以變成找B[1-5]大的子串滿足性質(zhì)（即前幾個(gè)與串開(kāi)頭幾個(gè)匹配），

  你會(huì)發(fā)現(xiàn)，這個(gè)東西其實(shí)上就是p[j]..(好吧，有點(diǎn)繞，這東西只能意會(huì)了。。)

  --------------------------夜深了，記點(diǎn)東西，明天繼續(xù)研究。。

網(wǎng)站名稱(chēng)：kmp小記-創(chuàng)新互聯(lián)
鏈接地址：http://bm7419.com/article46/ceoehg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、響應(yīng)式網(wǎng)站、關(guān)鍵詞優(yōu)化、App設(shè)計(jì)、標(biāo)簽優(yōu)化、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)