模式匹配的kmp算法

《模式匹配的kmp算法》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、模式匹配的kmp算法Kmp算法是由Knuth、Morris、Pratt與1969年夏天提出的快速串匹配算法，它是由對(duì)BF算法的很大改進(jìn)而成的，這主要體現(xiàn)在每當(dāng)某趟匹配失敗是，指針不必回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式向右“滑動(dòng)“若干個(gè)位置后繼續(xù)比較。由于KMP算法避免了BF算法中頻繁的回溯，普遍提高了模式匹配的工作效率，因此它又被稱(chēng)為“不回溯的字符串搜索算法”。假設(shè)有目標(biāo)串T(t0,t1,t2,t3……,tm-1)和模式串P(p０,p1,p2,p3,…pn-1),使用BF算法進(jìn)行模式匹配，當(dāng)進(jìn)行第一輪比較時(shí)，若tk≠pk

2、，則算法結(jié)束本輪比較，如下所示：Tt0,t1,t2,…tk,tk+1,…tn-2,tn-1,…tm-2,tm-1Pp0,p1,p2,…pk,pk+1…,pn-2,pn-1（第一輪比較結(jié)束）由于在字符串Ｔ與Ｐ中第一個(gè)不相等的字符位于ｋ處，所以?xún)勺址埃雮€(gè)字符是相等的。此時(shí)，可用字符串P(p0,p1,p2,p3,…pk-1)字符串T(t0,t1,t2,t3……,tk-1)，于是原目標(biāo)串可轉(zhuǎn)化為T(mén)(p0,p1,p2,p3,…pk-1，pk……,tm-1)。在進(jìn)行第二輪比較前，算法同樣把字符串P整體向后移動(dòng)一個(gè)字符，此時(shí)字符串T與P之間的關(guān)

3、系如下：Tp0,p1,p2,…pk-1,pk,…tn-2,tn-1,…tm-2,tm-1Pp0,p1,p2,…pk,pk+1…,pn-2,pn-1(第二輪比較)在第二輪比較中算法首先要比較的字符是P中首字符p0與T中第二個(gè)字符p1，若p0與p1相等，則算法順序比較P中第二個(gè)字符p1與T中第三個(gè)字符p2；若不等，則算法仍然把模式串P整體向后移動(dòng)一個(gè)字符，此時(shí)字符串T與P之間的關(guān)系如下Tp0,p1,p2,…pk-1,pk,…tn-2,tn-1,…tm-2,tm-1Pp0,…pk-3,pk-2,…,pn-1（第三次比較）算法依照同樣的次序，

4、首先對(duì)P中字符p0與T中字符p2進(jìn)行比較，若相等，則順序比較后續(xù)的字母；若不等，則把字符串P整體向后移動(dòng)一個(gè)字符。仔細(xì)考慮上述過(guò)程，可能會(huì)發(fā)現(xiàn)：在第二輪比較開(kāi)始是，首先進(jìn)行比較的字符是p0和p1，其次進(jìn)行的是p1和p2;在第三輪比較開(kāi)始時(shí)，首先進(jìn)行比較的是p0與p2，其次進(jìn)行的是p1和p3。而p0,p1,p2,p3全部是字符串P中的字符，它們之間的關(guān)系可以在調(diào)用字符串匹配算法前就確定下來(lái)。KMP算法正式利用這種思想，算法在對(duì)字符串進(jìn)行匹配前，先計(jì)算出，模式串P中個(gè)字符的關(guān)系，然后再依據(jù)此關(guān)系對(duì)模式串與目標(biāo)串T進(jìn)行匹配。在上述過(guò)程中，記

5、錄字符串P中各個(gè)字符之間關(guān)系的函數(shù)成為字符串P的失效函數(shù)。下面是失效函數(shù)獲取的辦法（對(duì)于P=“caatcat”）：首先確定函數(shù)的定義域，失效函數(shù)自變量j的取值范圍是模式串在失配前匹配的字符個(gè)數(shù)，那么它的定義域?yàn)閖{0,1,2,3,4,5}，由此可見(jiàn)失效函數(shù)的定義域是0-len（p）-1。接著是獲取失效函數(shù)值域的辦法，失效函數(shù)的取值k定義如下K{k

6、0<=k

7、：當(dāng)j=0時(shí)，由于0<=k<0,所以滿(mǎn)足條件的k并不存在，此時(shí)失效函數(shù)的取值為-1，即f(0)=-1.當(dāng)j=1時(shí)，k可能的取值為0，由于p0≠p1，所以k不能取0，此時(shí)滿(mǎn)足條件的失效函數(shù)的值仍為-1，即f(1)=-1。當(dāng)j=2時(shí)，k的可能取值為0,1。由于p0≠p2且p0p1≠p1p2，所以滿(mǎn)足條件的k不存在，即f(2)=-1。當(dāng)j=3時(shí)，k可能的取值為0,1,2。由于p0≠p3，p0p1≠p2p3且p0p1p2≠p1p2p3。所以滿(mǎn)足條件的k不存在，即f(3)=-1。當(dāng)j=4時(shí)，k可能的取值為0,1,2,3。由于p0=p4，p0p1

8、≠p3p4，p0p1p2≠p2p3p4且p0p1p2p3≠p1p2p3p4。所以滿(mǎn)足條件的k為0，此時(shí)f(4)=0。當(dāng)j=5時(shí)，k可能的取值為0,1,2,3,4。由于p0≠p5，p0p1=p4p5，p0p1p2≠p3p4p5，p0p1p2p3≠p2p3p4p5且p0p1p2p3p4≠p1p2p3p4p5，所以f(5)=1;同理可求當(dāng)j=6時(shí)，f(6)=-1。求完模式串p的失效函數(shù)后，就可以應(yīng)用KMP算法對(duì)它進(jìn)行匹配。具體的匹配過(guò)程分為兩種情況。假設(shè)在進(jìn)行某一輪比較時(shí)，失配的情況發(fā)生在模式p的第j位，那么如果j=0，則讓目標(biāo)的指針前進(jìn)一

9、位，模式串的起始比較地址回到P0處。否則，在進(jìn)行下一輪的比較時(shí)，目標(biāo)指針不發(fā)生回溯，仍指向失配的位置，而模式串的起始比較地址為Pf(j-1)+1.由失效函數(shù)的計(jì)算過(guò)程可見(jiàn)，函數(shù)f(j)僅與字符串P有關(guān)，而與目標(biāo)串無(wú)關(guān)。所