Chapter4_Kmp算法原理演示

1、KMP算法一、樸素的字符串匹配一、樸素的字符串匹配我們可以寫(xiě)出很容易實(shí)現(xiàn)的字符串匹配的算法，從A的起始位置和B的起始位置開(kāi)始比較，如果匹配不成功則從A原先起始位置的下一位開(kāi)始和B的起始位置開(kāi)始比較。如果A和B的字符個(gè)數(shù)分別是m和n，那么這個(gè)算法的效率是O(mn)，雖然大部分情況下不至于m*n次但還是有很多不幸的情況發(fā)生。一、樸素的字符串匹配一、樸素的字符串匹配設(shè)A=“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab” B=“aaaaaaaab”按照樸素算法，每次比到B的最后一位發(fā)現(xiàn)不同又要重新從B的開(kāi)頭和A的下一個(gè)字符開(kāi)始比較。一、樸素的字符串匹配一、樸素的字符串匹配樸素算法

2、中不可避免的存在“回溯”現(xiàn)象，因此降低了算法的效率，下面介紹的是一種最壞情況下O(n)的算法（這里假設(shè) m=n），即傳說(shuō)中的KMP算法。二、算法概述二、算法概述KMP算法是用來(lái)處理字符串匹配的。換句話說(shuō)，給你兩個(gè)字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。例如”Today is Tuesday”.中是否包含”day”，在哪些位置包含。這個(gè)算法是由Knuth、Morris、Pratt三個(gè)提出來(lái)的，取了這三個(gè)人的名字的頭一個(gè)字母。二、算法概述二、算法概述假如，A=abababaababacb，B=ababacb，我們來(lái)看看KMP是怎么工作的。我們用兩個(gè)指針i和j分別表示，Ai-j

3、+ 1.i與B1.j完全相等。也就是說(shuō)，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以Ai結(jié)尾的長(zhǎng)度為j的字符串正好匹配B串的前 j個(gè)字符（j當(dāng)然越大越好），現(xiàn)在需要檢驗(yàn)Ai+1和Bj+1的關(guān)系。當(dāng)Ai+1=Bj+1時(shí)，i和j各加一；什么時(shí)候j=m了，我們就說(shuō)B是A的子串（B串已經(jīng)整完了），并且可以根據(jù)這時(shí)的i值算出匹配的位置。二、算法概述二、算法概述當(dāng)Ai+1Bj+1，KMP的策略是調(diào)整j的位置（減小j值）使得Ai-j+1.i與B1.j保持匹配且新的Bj+1恰好與Ai+1匹配（從而使得i和j能繼續(xù)增加）。我們看一看當(dāng) i=j=5時(shí)的情況。位置。i: 1 2 3 4 5 6 7 8 9

4、10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述從上面的這個(gè)例子，我們可以看到，新的j可以取多少與i無(wú)關(guān)，只與B串有關(guān)。我們完全可以預(yù)處理出這樣一個(gè)數(shù)組Pj，表示當(dāng)匹配到B數(shù)組的第j個(gè)字母而第j+1個(gè)字母不能匹配了時(shí)，新的j最大是多少。Pj

5、應(yīng)該是所有滿足B1.Pj=Bj-Pj+1.j的最大值。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述此時(shí)，A7=B5，又出現(xiàn)Ai+1Aj+1的情況，由于P5=3，所以j=3。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10

6、i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述此時(shí)，i=7,j=3,依舊Ai+1Aj+1，我們將j的值改為P3=1。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b

7、 a b a c bj: 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述依舊Ai+1Aj+1，我們將j的值改為P1=0。A: a b a b a b a a b a b i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 1 2 3 4 5 6 7 8 9 10i: 1 2 3 4 5 6 7 8 9 10A: a b a b a b a a b a b B: a b a b a c bj: 0 1 2 3 4 5 6 7 8 9 10二、算法概述二、算法概述i: 1 2 3 4 5 6 7 8

8、 9 10A: a b a b a b a a b a b B: a b a b a c bj: 0 1 2 3 4 5 6 7 8 9 10終于，A8=B1，i變?yōu)?，j為1。事實(shí)上，有可能j到了0仍然不能滿足Ai+1=Bj+1（比如A8=d時(shí)）。因此，準(zhǔn)確的說(shuō)法是，當(dāng)j=0了時(shí)，我們?cè)黾觟值但忽略j直到出現(xiàn)Ai=B1為止。二、算法概述二、算法概述【算法實(shí)現(xiàn)】最后的j:=Pj是為了讓程序繼續(xù)做下去，因?yàn)槲覀冇锌赡苷业蕉嗵幤ヅ洹?這個(gè)程序或許比想像中的要簡(jiǎn)單，因?yàn)閷?duì)于i值的不斷增加，代碼用的是for循環(huán)。因此，這個(gè)代碼可以這樣形象地理解：掃描字符串A，并更新可以匹配到B的什么位置。 j:=0;

9、 for i:=1 to m do begin while (j0)and(aibj+1) do j:=Pj; if ai=bj+1 then inc(j); if j=n then begin writeln(Found at ,i-n+1); j:=Pj; end; end;二、算法概述二、算法概述在此我們應(yīng)該注意一個(gè)現(xiàn)象，Pi的值既是B串前i個(gè)中的最大相同前后綴的個(gè)數(shù)。B: a b a b a c bP: 0 0 1 2 3 求P數(shù)組的值二、算法概述二、算法概述預(yù)處理不需要按照P的定義寫(xiě)成O(m2)甚至O(m3)的。我們可以通過(guò)P1,P2,.,Pj-1的值來(lái)獲得Pj的值。對(duì)于剛才的B=“

10、ababacb”，假如我們已經(jīng)求出了P1,P2,P3和P4，看看我們應(yīng)該怎么求出P5和P6。B: a b a b a c bP: 0 0 1 2求P數(shù)組的值由于P4=2，可知B3.4=B1.2，由于B5=B3=a，所以可知P5=33B: a b a b a c b二、算法概述二、算法概述現(xiàn)在求P6。由于P5=3，可知B3.5=B1.3求P數(shù)組的值B6B4，沒(méi)有找到相同的前后綴，那么我們能否退而求其次，看在更小的范圍內(nèi)是否能找到Bi+1=Bj+1的情況。在P5=3的范圍內(nèi)能保證的最大相同前后綴是P3=1，因此我們對(duì)齊，再做嘗試，仍然不行，直到P6=0B: a b a b a c bP: 0 0

11、1 2 3B: a b a b a c bB: a b a b a c bP: 0 0 1 2 3B: a b a b a c b0二、算法概述二、算法概述怎么這個(gè)預(yù)處理過(guò)程跟前面的KMP主程序這么像呢？其實(shí)，KMP的預(yù)處理本身就是一個(gè)B串“自我匹配”的過(guò)程。它的代碼和上面的代碼神似：求P數(shù)組的值 P1:=0;j:=0; for i:=2 to n do begin while (j0)and(bibj+1) do j:=Pj; if bi=bj+1 then inc(j); Pi:=j; end;三、算法分析三、算法分析為什么這個(gè)程序是O(n)的？其實(shí)，主要的爭(zhēng)議在于，while循環(huán)使得執(zhí)行

12、次數(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ò)

13、程顯然是O(n)的。這樣的分析對(duì)于后面P數(shù)組預(yù)處理的過(guò)程同樣有效，同樣可以得到預(yù)處理過(guò)程的復(fù)雜度為O(m)。四、算法應(yīng)用四、算法應(yīng)用 最后補(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í)間里解決字符串的匹配。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2next數(shù)組的求解方法是：第一位的next值為0，第二位的next值為1，后面求解每

14、一位的next值時(shí)，根據(jù)前一位進(jìn)行比較。首先將前一位與其next值對(duì)應(yīng)的內(nèi)容進(jìn)行比較，如果相等，則該位的next值就是前一位的next值加上1；如果不等，向前繼續(xù)尋找next值對(duì)應(yīng)的內(nèi)容來(lái)與前一位進(jìn)行比較，直到找到某個(gè)位上內(nèi)容的next值對(duì)應(yīng)的內(nèi)容與前一位相等為止，則這個(gè)位對(duì)應(yīng)的值加上1即為需求的next值；如果找到第一位都沒(méi)有找到與前一位相等的內(nèi)容，那么需求的位上的next值即為1。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 21.前兩位必定為0和1。2.計(jì)算第三位的時(shí)候，看第二位b的next值，為1，則把b和1對(duì)應(yīng)的a進(jìn)行

15、比較，不同，則第三位a的next的值為1，因?yàn)橐恢北鹊阶钋耙晃?，都沒(méi)有發(fā)生比較相同的現(xiàn)象。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 23.計(jì)算第四位的時(shí)候，看第三位a的next值，為1，則把a(bǔ)和1對(duì)應(yīng)的a進(jìn)行比較，相同，則第四位a的next的值為第三位a的next值加上1。為2。因?yàn)槭窃诘谌粚?shí)現(xiàn)了其next值對(duì)應(yīng)的值與第三位的值相同。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 24.計(jì)算第五位的時(shí)候，看第四位a的next值，為2，則把a(bǔ)和2對(duì)應(yīng)的b進(jìn)行比較

16、，不同，則再將b對(duì)應(yīng)的next值1對(duì)應(yīng)的a與第四位的a進(jìn)行比較，相同，則第五位的next值為第二位b的next值加上1，為2。因?yàn)槭窃诘诙粚?shí)現(xiàn)了其next值對(duì)應(yīng)的值與第四位的值相同。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 25.計(jì)算第六位的時(shí)候，看第五位b的next值，為2，則把b和2對(duì)應(yīng)的b進(jìn)行比較，相同，則第六位c的next值為第五位b的next值加上1，為3，因?yàn)槭窃诘谖逦粚?shí)現(xiàn)了其next值對(duì)應(yīng)的值與第五位相同。next值的求法值的求法例如： 模式串 a b a a b c a c next值 0 1 1 2 2

17、3 1 2 6.計(jì)算第七位的時(shí)候，看第六位c的next值，為3，則把c和3對(duì)應(yīng)的a進(jìn)行比較，不同，則再把第3位a的next值1對(duì)應(yīng)的a與第六位c比較，仍然不同，則第七位的next值為1。7.計(jì)算第八位的時(shí)候，看第七位a的next值，為1，則把a(bǔ)和1對(duì)應(yīng)的a進(jìn)行比較，相同，則第八位c的next值為第七位a的next值加上1，為2，因?yàn)槭窃诘谄呶缓蛯?shí)現(xiàn)了其next值對(duì)應(yīng)的值與第七位相同。nextval值的求法值的求法例如主串為“aaabaaaab”、 模式串為“aaaab”在計(jì)算nextval之前要先弄明白，nextval是為了彌補(bǔ)next函數(shù)在某些情況下的缺陷而產(chǎn)生的。例如主串為“aaabaaa

18、ab”、模式串為“aaaab”那么，比較的時(shí)候就會(huì)發(fā)生一些浪費(fèi)的情況：比較到主串以及模式串的第四位時(shí)，發(fā)現(xiàn)其值并不相等，據(jù)我們觀察，我們可以直接從主串的第五位開(kāi)始與模式串進(jìn)行比較，而事實(shí)上，卻進(jìn)行了幾次多余的比較。使用nextval可以去除那些不必要的比較次數(shù)。nextval值的求法值的求法例如主串為“aaabaaaab”、 模式串為“aaaab”求nextval數(shù)組值有兩種方法，一種是不依賴next數(shù)組值直接用觀察法求得，一種方法是根據(jù)next數(shù)組值進(jìn)行推理，兩種方法均可使用，視更喜歡哪種方法而定。nextval值的求法值的求法模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2 nextval值 0 1 0 2 1 3 0 21.第一位的nextval值必定為0，第二位如果于第一位相同則為0，如果不同則為