KMP算法(改進版)5頁

1、4.3.2 模式匹配的一種改進算法這種改進算法是D.E.Knuth與V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)的，因此人們稱它為克努特莫里斯普拉特操作（簡稱KMP算法）。此算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配操作。其改進在于：每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。下面先從具體例子看起。 i=3第一趟匹配 a b a b c a b c a c b a b a b c j=3 i3第二趟匹配 a b a b c a b c a c b a b a b c a c j=5

2、 j=1 i i=11第三趟匹配 a b a b c a b c a c b a b (a)b c a c j=6回顧4.3的匹配過程示例，在第三趟的匹配中，當(dāng)i=7、j=5字符比較不等時，又從i=4、j=1重新開始比較。然后，經(jīng)仔細觀察可發(fā)現(xiàn)，在i=4和j=1，i=5和j=1以及i=6和j=1這三次比較都是不必進行的。因為從第三趟部分匹配的結(jié)果就可以得出，主串中第4、5和6個字符必然是b、c和a（即模式串中第2、3和4個字符）。因為模式中的第一個字符是a，因此它無需再和這三個字符進行比較，而僅需將模式向右滑動三個字符的位置繼續(xù)進行比較i=7、j=2的字符比較即可。同理，在第一趟匹配中出現(xiàn)字符

3、不等時，僅需將模式向右滑動兩個字符的位置繼續(xù)進行i=3、j=1時的字符比較。由此，在整個匹配的過程中，i指針沒有回溯，如圖4.4所示。現(xiàn)在討論一般情況。假設(shè)主串位s1s2sn，模式串為p1p2pm，從上例的分析可知，為實現(xiàn)改進算法，需要解決下述問題：當(dāng)匹配過程中產(chǎn)生“失配”（即sipj）時，模式串“向右滑動”可行的距離有多遠，換句話說，當(dāng)主串中第i個字符與模式中第j個字符“失配”（即比較不等）時，主串中第i個字符（i指針不回溯）應(yīng)與模式中哪個字符再比較？假設(shè)此時應(yīng)與模式中第k（kk，滿足下列關(guān)系式（4-2）p1p2pk-1=si-k+1s i-k+2si-1 (4-2)而已經(jīng)得到的“部分匹配”

4、的結(jié)果是pj-k+1p j-k+2p j-1=si-k+1s i-k+2si-1 (4-3)由(4-2)和(4-3)推得下列等式p1p2pk-1=pj-k+1p j-k+2p j-1 (4-4)反之，若模式串中存在滿足式(4-4)的兩個字串，則當(dāng)匹配過程中，主串中第i個字符與模式中第j個字符比較不等時，僅需將模式向右滑動至模式中第k個字符和主串中第i個字符對齊，此時，模式中頭k-1個字符的字串p1p2pk-1必定與主串中第i個字符之前長度為k-1的字串si-k+1s i-k+2si-1相等，由此，匹配僅需從模式中第k個字符與主串中第i個字符比較起繼續(xù)進行。若令nextj=k，則nextj表明當(dāng)

5、模式中第i個字符與主串中相應(yīng)字符“失配”時，在模式中需重新和該字符進行比較的字符的位置。由此可引出模式串的next函數(shù)的定義： 0 當(dāng)j=1時nextj= maxk|1kj且p1pk-1=pj-k+1p j-k+2p j-1 (4-5)1 其它情況由此定義可推出下列模式串的next函數(shù)值j12345678模式串a(chǎn)baabcacnextj01122312在求得模式的next函數(shù)之后，匹配可如下進行：假設(shè)以指針i和j分別指示主串好模式中正待比較的字符，令i的初值為pos，j的初值為1,。若在匹配過程中si=pj，則i和j分別增1，否則，i不變，而j退到nextj的位置再比較。若相等，則指針各自增1

6、，否則，j再退到nextj的位置再比較，若相等，則指針各自增1，繼續(xù)進行匹配；另一種是j退到某個next值(nextnextnextj)時字符比較相等，則指針各自增1，繼續(xù)進行匹配；另一種是j退到0(即模式的第一個字符“失配”)，則此時須將模式繼續(xù)向右滑行一個位置，即從主串的下一個字符s i+1起模式重新開始匹配。圖4.5所示正是上述匹配過程的一個例子。 i=2第一趟 主串 a c a b a a b a a b c a c a a b c模式 a b j=2 next2=1 i=2第二趟 主串 a c a b a a b a a b c a c a a b c模式 a j=1 next1=0

7、 i=3第三趟 主串 a c a b a a b a a b c a c a a b c模式 a b a a b c j=1j=6 next6=3 i=8 i=14第四趟 主串 a c a b a a b a a b c a c a a b c模式 (a b)a a b c a c j=3 j=9KMP算法如算法4.6所示，它在形式上和算法4.5極為相似。不同之處僅在于：當(dāng)匹配過程中產(chǎn)生“失配”是，指針i不變，指針j退到nextj所指示的位置上重新進行比較，并且當(dāng)指針j退至0時，指針i和指針j需同時增1。即若主串的第i個字符和模式的第1個字符不等，應(yīng)從主串的第i+1個字符起重新進行匹配。int

8、 index_KMP(SString S,SString T,int pos) /利用模式串T的next函數(shù)求T在主串S中第pos個字符之后的位置的 / KMP算法。其中T非空，1posStrLength(S)。 i=pos; j=1;while ( i=S 0 & jT 0 ) return i-T 0 ; else return 0;算法4.6KMP算法是在已知模式串的next函數(shù)值的基礎(chǔ)上執(zhí)行的，那么，如何求得模式串的next函數(shù)值呢？從上述討論可見，此函數(shù)值僅取決于模式串本身而和相匹配的主串無關(guān)。我們可從分析其定義出發(fā)用遞推的方法求得next函數(shù)值。由定義得知 next1=0 (4-6

9、)設(shè)nextj=k，這表明在模式串中存在下列關(guān)系： p1pk-1=pj-k+1p j-1 (4-7)其中k為滿足1kk，滿足等式(4-7)。此時nextj+1=？可能有兩種情況：(1) 若pk=pj，則表明在模式串中 p1pk-1=pj-k+1pj-1 (4-8)并且不可能存在kk滿足等式(4-8)，這就是說nextj+1=k+1，即 nextj+1= nextj+1 (4-9)(2) 若pkpj，則表明在模式串中p1pk-1 pj-k+1p j-1此時可把求next函數(shù)值的問題看成是一個模式匹配的問題，整個模式串即使主串有是模式串，而當(dāng)前在匹配的過程中，已有pj-k+1=p1，pj-k+2=

10、p2，pj-1=pk-1，則當(dāng)pjpk時，應(yīng)將模式向右滑動已知模式中的第nextk個字符和主串中的第j個字符相比較。若nextk=k，且pj=pk，則說明在主串中第j+1個字符之前存在一個長度為k(即next k)的最長字串，和模式串中從首字符起長度為k的字串相等，即 p1pk=pj-k+1pj-1 (1kkj) (4-10)這就是說 nextj+1= k+1即 nextj+1= nextk+1 (4-11)同理，若pjpk，則將模式繼續(xù)向右滑動直至將模式中第nextk個字符和pj對齊，依次類推，直至pj和模式中某個字符匹配成功或者不存在任何k(1kj)滿足等式(4-10)，則 nextj+1

11、= 1 (4-12)例如：圖4.6中的模式串，已求得前6個字符的next函數(shù)值，先求next7，因為next6=3，又p6p3，則需比較p6與p1(因為next3=1)，這相當(dāng)于將字串模式向右滑動。由于p6p1，而且next1=0，所以next7=1，而因為p7=p1，則next8=2。根據(jù)上述分析所得結(jié)果(式(4-6)、(4-9)、(4-11)和(4-12)，仿照KMP算法，可求得next函數(shù)值的算法，如算法4.6所示。void get_next(SString T,int &next ) /求模式串T的next函數(shù)值并存入數(shù)組next。 i=1; next 1 =0; j=0; while

12、 ( iT 0 ) if ( j=0 | T i =T j ) i+; j+; next i =k; else j=next j ; /get_next算法 4.7算法4.7的時間復(fù)雜度為o(m)。通常，模式串的長度m比主串的長度n要小得多，因此，對整個匹配算法來說，所增加的這點時間是值得的。最后，要說明兩點：1） 雖然算法4.5的時間復(fù)雜度是o(n*m),但在一般情況下，其實際的執(zhí)行時間近似于o(n+m),但因此至今仍被采用。Kmp算法僅當(dāng)模式與主串之間存在許多“部分匹配”的情況下才顯得比算法4.5快很多。但是kmp算法的最大特點是指示主串的指針不需回溯，整個匹配過程中，對主串僅需從頭至尾掃

13、描一遍，這對處理從外設(shè)輸入的龐大文件很有效，可以邊讀入邊匹配，而無需回頭重讀。2） 前面定義的next函數(shù)在某些情況下尚有缺陷。例如模式a a a a b在和主串a(chǎn) b a a a a b 匹配時，當(dāng)i=4,j=4時s.ch4 t.ch4,由nextj的指示還需要進行i=4、j=3,i=4、j=2,i=4、j=1等三次比較。實際上，因為模式中第1、2、3個字符和第4個字符都相等，因此不需要再和主串中第4個字符相比較，而可以將模式一氣向右滑動4個字符的位置直接進行i=5、j=1時的字符比較。這就是說，若按上述定義得出nextj=k,而模式中pj = pk ,則當(dāng)主串中字符si和pj比較不等時，不需要再和pk進行比較，而直接和pnextk進行比較，換句話說，此時的nextj應(yīng)和nextk相同。由此可得計算next函數(shù)修正值的算法如算法4.8所示。此時匹配算法不變。 void get_nextval(SSt