KMP算法詳解介紹

1、KMFlf法詳解介紹KMF!?法，是由Knuth,Morris,Pratt共同提出的模式匹配算法，其對(duì)于任何模式和目標(biāo)序列，都可以在線(xiàn)性時(shí)間內(nèi)完成匹配查找，而不會(huì)發(fā)生退化，是一個(gè)非常優(yōu)秀的模式匹配算法。但是相較于其他模式匹配算法，該算法晦澀難懂，第一次接觸該算法的讀者往往會(huì)看得一頭霧水，主要原因是KMPW法在構(gòu)造跳轉(zhuǎn)表next過(guò)程中進(jìn)行了多個(gè)層面的優(yōu)化和抽象，使得KMPff法進(jìn)行模式匹配的原理顯得不那么直白。本文希望能夠深入KMPW法，將該算法的各個(gè)細(xì)節(jié)徹底講透，掃除讀者對(duì)該算法的困擾。KMPW法對(duì)于樸素匹配算法的改進(jìn)是引入了一個(gè)跳轉(zhuǎn)表next。以模式字符串a(chǎn)bcabcacab為例，其跳轉(zhuǎn)表為

2、：j1123456718910patternjabcabcacabnextj01101101 501跳轉(zhuǎn)表的用途是， 當(dāng)目標(biāo)串target中的某個(gè)子部targetm.m+(i-1)與pattern串的前i個(gè)字符pattern1.i相匹配時(shí)，如果targetm+i與patterni+1匹配失敗，程序不會(huì)像樸素匹配算法那樣，將pattern1與targetm+1對(duì)其，然后由targetm+1向后逐一進(jìn)行匹配，而是會(huì)將模式串向后移動(dòng)i+1-nexti+1個(gè)字符，使得patternnexti+1與targetm+i對(duì)齊，然后再由targetm+i向后與依次執(zhí)行匹配。舉例說(shuō)明，如下是使用上例的模式串對(duì)目

3、標(biāo)用執(zhí)行匹配的步驟1234567891011121314151617181920212223242526babcbabcabcaabcabcab cac abcabcabcacababcabcacababcabcacababcabcacababcabcac ababcabcac ab通過(guò)模式用的5次移動(dòng)，完成了對(duì)目標(biāo)串的模式匹配。這里以匹配的第3步為例，此時(shí)pattern串的第1個(gè)字母與target6對(duì)齊，從6向后依次匹配目標(biāo)串，至Utarget13時(shí)發(fā)現(xiàn)target13=a,而pattern8=c,匹配失敗， 此時(shí)next8=5,所以將模式串向后移動(dòng)8-next8=3個(gè)字符，將pattern

4、5與target13對(duì)齊，然后由target13依次向后執(zhí)行匹配操作。在整個(gè)匹配過(guò)程中，無(wú)論模式串如何向后滑動(dòng)，目標(biāo)用的輸入字符都在不會(huì)回溯，直到找到模式串，或者遍歷整個(gè)目標(biāo)串都沒(méi)有發(fā)現(xiàn)匹配模式為止。next跳轉(zhuǎn)表，在進(jìn)行模式匹配，實(shí)現(xiàn)模式串向后移動(dòng)的過(guò)程中，發(fā)揮了重要作用。這個(gè)表看似神奇，實(shí)際從原理上講并不復(fù)雜，對(duì)于模式串而言，其前綴字符串，有可能也是模式串中的非前綴子串，這個(gè)問(wèn)題我稱(chēng)之為前綴包含問(wèn)題。以模式用abcabcacab為例，其前綴4abca,正好也是模式用的一個(gè)子串a(chǎn)bc(abca)cab,所以當(dāng)目標(biāo)串與模式串執(zhí)行匹配的過(guò)程中，如果直到第8個(gè)字符才匹配失敗，同時(shí)也意味著目標(biāo)用當(dāng)前

5、字符之前的4個(gè)字符，與模式用的前4個(gè)字符是相同的，所以當(dāng)模式串向后移動(dòng)的時(shí)候，可以直接將模式用的第5個(gè)字符與當(dāng)前字符對(duì)齊，執(zhí)行比較，這樣就實(shí)現(xiàn)了模式用一次性向前跳躍多個(gè)字符。所以next表的關(guān)鍵就是解決模式用的前綴包含。當(dāng)然為了保證程序的正確性，對(duì)于next表的值，還有一些限制條件，后面會(huì)逐一說(shuō)明。如何以較小的代價(jià)計(jì)算KMFW法中所用到的跳轉(zhuǎn)表next,是算法的核心問(wèn)題。這里我們引入一個(gè)概念f(j),其含義是，對(duì)于模式串的第j個(gè)字符patternj，的)是所有滿(mǎn)足使pattern1.k-1=patternj-(k-1).j-1(kj)成立的k的最大值。還是以模式用abcabcacab為例，當(dāng)處

6、理到pattern8=c時(shí)，我們想找到c前面的k-1個(gè)字符，使得pattern1.k-1=pattern8-(k-1).7,這里我們可以使用一個(gè)笨法，讓k-1從1到6遞增，然后依次比較，直到找到最大值的k為止，比較過(guò)程如下k-1前綴關(guān)系子用1a=a211ab!=ca3abc!=bca4abca=abca5abcab!=cabca6abcabc=bcabca因?yàn)橐∽畲蟮膋,所以k-1=1不是我們要找的結(jié)果，最后求出k的最大值為4+1=5。但是這樣的方法比較低效，而且沒(méi)有充分利用到之前的計(jì)算結(jié)果。在我們處理pattern8=c之前，pattern7=a的最大前綴包含問(wèn)題已經(jīng)解決，f(7)=4,也

7、就是說(shuō)，pattern4.6=pattern1.3,此時(shí)我們可以比較pattern7與pattern4,如果pattern4=pattern7,對(duì)于pattern8而言， 說(shuō)明pattern1.4=pattern4.7,此時(shí)，f(8)=f(7)+1=5。再以pattern9為例，f(8)=5,pattern1.4=pattern4.7,但是pattern8!=pattern5,所以pattern1.5!=pattern4.8,此時(shí)無(wú)法利用f(8)的值直接計(jì)算出f(9)。j123456789 10patternjabcabcacabnextj0110110501f(j)二0111234512我們

8、可能考慮還是使用之前的笨方法來(lái)求出f(9),但是且慢，利用之前的結(jié)果，我們還可以得到更多的信息。還是以pattern8為例。f(8)=5,pattern1.4=pattern4.7,此時(shí)我們需要關(guān)注pattern8,如果pattern8!=pattern5,那么在匹配算法如果匹配到pattern8才失敗，此時(shí)就可以將輸入字符targetn與patternf(8)=pattern5對(duì)齊，再向后依次執(zhí)行匹配，所以此時(shí)的next8=f(8)(此平移的正確性，后面會(huì)作出說(shuō)明)。而如果pattern8=pattern5,那么pattern1.5=pattern4.8，如果targetn與pattern8

9、匹配失敗，那么同時(shí)也意味著targetn-5.n!=pattern4.8,那么將targetn與pattern5對(duì)齊，targetn-5.n也 必 然 不 等 于pattern1.5, 此 時(shí) 我 們 需 要 關(guān) 注f(5)=2,這 意 味 著pattern1=pattern4,因 為pattern1.4=pattern4.7,所以pattern4=pattern7=pattern1,此時(shí)我們?cè)賮?lái)比較pattern8與pattern2,如果pattern8!=pattern2,就可以將targetn與pattern2,然后比較二者是否相等，此時(shí)next8=next5=f(2)。如果patter

10、n8=pattern2,那么還需要考察patternf(2),直到回溯到模式串頭部為止。下面給出根據(jù)f(j)值求nextj的遞推公式：如果patternj!=patternf(j),nextj=f(j);如果patternj=patternf(j),nextj=nextf(j);當(dāng)要求f(9)時(shí)，f(8)和next8已經(jīng)可以得到，此時(shí)我們可以考察patternnext8,根據(jù)前面對(duì)于next值的計(jì)算方式，我們知道pattern8!=patternnext8。我們的目的是要找到pattern9的包含前綴，而pattern8!=pattern5,pattern1.5!=pattern4.8。我們繼

11、續(xù)考察patternnext5。如果pattern8=patternnext5,假設(shè)next5=3,說(shuō)明pattern1.2=pattern6.7,且pattern3=pattern8,此時(shí)對(duì)于pattern9而言，就有pattern1.3=pattern6.8,我們就找到了f(9)=4。這里我們考察的是patternnextj,而不是patternf(j),這是因?yàn)閷?duì)于next而言，patternj!=patternnextj,而對(duì)于f()而言，patternj與patternf(j)不一定不相等，而我們的目的就是要在patternj!=patternf(j)的情況下，解決f(j+1)的問(wèn)題

12、，所以使用nextj向前回溯，是正確的?，F(xiàn) 在 ， 我 們 來(lái) 總 結(jié) 一 下nextj和f(j)的 關(guān) 系 ，nextj是 所 有 滿(mǎn) 足pattern1.k-1=pattern(j-(k-1).j-1(kj),且patternk!=patternj的k中，k的最大值。而f(j)是滿(mǎn)足pattern1.k-1=pattern(j-(k-1).j-1(kj)的k中，k的最大值。還是以上例的模式來(lái)說(shuō)，對(duì)于第7個(gè)元素，其f(j)=4,說(shuō)明pattern7的前3個(gè)字符與模式的前綴3相同，但是由于pattern7=pattern4,所以next7!=4。通過(guò)以上這些，讀者可能會(huì)有疑問(wèn)，為什么不用f(j

13、)直接作為KMPT法的跳轉(zhuǎn)表呢？實(shí)際從程序正確性的角度講是可以的，但是使用nextj作為跳轉(zhuǎn)表更加高效。還是以上面的模式為例，當(dāng)targetn與pattern7發(fā)生匹配失敗時(shí)，根據(jù)f(j),targetn要繼續(xù)與pattern4進(jìn)行比較。但是在計(jì)算f(8)的時(shí)候，我們會(huì)得出pattern7=pattern4,所以targetn與pattern4的比較也必然失敗，所以targetn與pattern4的比較是多余的，我們需要targetn與更小的pattern進(jìn)行比較。當(dāng)然使用f(j)作為跳轉(zhuǎn)表也能獲得不錯(cuò)的性能，但是KMPE人將問(wèn)題做到了極致。我們可以利用f(j)作為媒介，來(lái)遞推模式的跳轉(zhuǎn)表ne

14、xt。算法如下：cppviewplaincopy1.inlinevoidBuildNext(constchar*pattern,size_tlength,unsignedint*next)2.3.unsignedinti,t;4.5.i=1;6.t=0;7.next1=0;8.9.while(i0&patterni-1!=patternt-1)12.13.t=nextt;14.15.16.+t;17.+i;18.19.if(patterni-1=patternt-1)20.21.nexti=nextt;22.23.else24.25.nexti=t;26.27.28.29./patte

15、rn末尾的結(jié)束符控制，用于尋找目標(biāo)字符串中的所有匹配結(jié)果用30.while(t0&patterni-1!=patternt-1)31.32.t=nextt;33.34.35.+t;36.+i;38.nexti=t;39.程序中，9到27行的循環(huán)需要特別說(shuō)明一下，我們發(fā)現(xiàn)在循環(huán)開(kāi)始之后，就沒(méi)有再為t賦新值，也就是說(shuō)，對(duì)于計(jì)算nextj時(shí)的t值，在計(jì)算nextj+1時(shí)，還會(huì)用得著。實(shí)際這時(shí)的t的就等于f(j)。還是以上例的目標(biāo)串為例，當(dāng)j等于1,我們可以得出t=f(2)=1。使用歸納法，當(dāng)計(jì)算完nextj后，我們假設(shè)此時(shí)t=f(j),此時(shí)第1114行的循環(huán)就是要找到滿(mǎn)足patternk=p

16、atternj的最大k值。如果這樣的k存在，對(duì)于patternj+1而言，其前k個(gè)元素，與模式的前綴k相同。此時(shí)的t+1就是f(j+1)。這時(shí)我們就要判斷patternj+1和patternt(t=t+1)的關(guān)系，然后求出nextj+1。這里需要初始條件next1=0。利用跳轉(zhuǎn)表實(shí)現(xiàn)字符串匹配的算法如下：cppviewplaincopy1.unsignedintKMP(constchar*text,size_ttext_length,constchar*pattern,size_tpattern_length,unsignedint*matches)2.3.unsignedinti,j,n;4

17、.unsignedintnextpattern_length+2;5.6.BuildNext(pattern,pattern_length,next);7.8.i=0;9.j=1;10.n=0;11.12.while(pattern_length+1-j=text_length-i)13.14.if(texti=patternj-1)15.16.+i;17.+j;18.19./發(fā)現(xiàn)匹配結(jié)果，將匹配子串的位置，加入結(jié)果20.if(j=pattern_length+1)21.22.matchesn+=i-pattern_length;23.j=nextj;24.25.26.else27.if(j=

18、0)(+i;+j;/返回發(fā)現(xiàn)的匹配數(shù)returnn;該算法在原有基礎(chǔ)上進(jìn)行了擴(kuò)展，在原模式串末尾加入了一個(gè)“空字符”，“空字符”不等于任何的可輸入字符，當(dāng)目標(biāo)串匹配至“空字符”時(shí)，說(shuō)明已經(jīng)在目標(biāo)字符串中發(fā)現(xiàn)了模式，將模式用在目標(biāo)串中的位輅，加入matchs口數(shù)組中，同時(shí)判定為匹配失敗，并根據(jù)“空字符”的next值，跳轉(zhuǎn)到適當(dāng)位輅，這樣算法就可以識(shí)別出字符串中所有的匹配子串。最后，對(duì)KMPT法的正確性做一簡(jiǎn)要說(shuō)明，還是以上文的模式串pattern和目標(biāo)用target為例，假設(shè)已經(jīng)匹配到第3部的位輅，且在target13處發(fā)現(xiàn)匹配失敗，我們?nèi)绾螞Q定模式串的滑動(dòng)步數(shù)，來(lái)保證既要忽略不必要的多余比較，

19、又不漏過(guò)可能的匹配呢？對(duì)于例子中的情況，顯然向后移動(dòng)多于3個(gè)字符有可能會(huì)漏過(guò)target9.18這樣的的可能匹配。 但是為什么向后移動(dòng)1個(gè)或者2個(gè)字符是不必要的多余比較呢？當(dāng)target13與pattern8匹配失敗時(shí)，同時(shí)也意味著，target6.12=pattern1.7,而next8=5,意味著，pattern1.4=pattern4.7,pattern1.5!=pattern3.7,pattern1.6!=pattern2.7。如果我們將模式串后移1個(gè)字符，使pattern7與target13對(duì)齊，止匕時(shí)target7.12相當(dāng)于pattern2.7,且target7.12與patte

20、rn1.6逐個(gè)對(duì)應(yīng)，而我們已經(jīng)知道pattern1.6!=pattern2.7。 所以不管target13是否等于pattern7,此次比較都必然失敗。 同理向前移動(dòng)2個(gè)字符也是多余的比較。由此我們知道當(dāng)在patternj處發(fā)生匹配失敗時(shí)，將當(dāng)前輸入字符與patternj和patternnextj之間的任何一個(gè)字符對(duì)齊執(zhí)行的匹配嘗試都是必然失敗的。這就說(shuō)明，在模式串從目標(biāo)串頭移動(dòng)到目標(biāo)串末尾的過(guò)程中，除了跳過(guò)了必然失敗的情況之外，沒(méi)有漏掉任何一個(gè)可能匹配，所以KMFB法的正確性是有保證的。28.j=nextj;29.30.31.32.33.34.35.36.37.38.39.40.后記：首先要感謝Knuth-Morr