模式匹配KMP 算法思想分析

任憲臻 任美玲

(1.北京信息職業(yè)技術(shù)學(xué)院 軟件與信息學(xué)院，北京 100018；2.煙臺南山學(xué)院 工學(xué)院計(jì)算機(jī)系，山東 煙臺 265700)

KMP 算法由 Knuth、Morris 和 Pratt 共同提出并設(shè)計(jì)的模式匹配改進(jìn)算法，稱之為 Knuth-Morris-Pratt 算法，簡稱 KMP 算法。KMP 算法對BF 算法做了很大的改進(jìn)。分析BF 算法的執(zhí)行過程，造成BF 算法效率低的原因是回溯，即在某趟匹配失敗后，對于主串S 要回溯到本趟匹配開始字符的下一個(gè)字符，模式T 要回溯到第一個(gè)字符，而這些回溯往往是不必要的。若主串S=“ababcabcacbab”，模式T=“abcac”，現(xiàn)在我們來分析一下在BF 算法，在哪些情況下回溯是沒有必要的。主串S 和模式T 的表示如下圖1 所示。

圖1 主串S 和模式T

第一趟匹配：開始下標(biāo)i=0，j=0，當(dāng)i=2，j=2 時(shí)匹配失敗。利用本趟部分匹配的結(jié)果：S[1]=T[1]且T[0]≠T[1]，我們可以得到這樣的關(guān)系：S[1]≠ T[0]。

第二趟匹配：如果需要進(jìn)行，則應(yīng)該是從開始下標(biāo)i=1，j=0 開始，但是利用第一趟匹配中得到的結(jié)果S[1]≠ T[0]，所以第二趟匹配是沒有必要進(jìn)行的。

第三趟匹配：因?yàn)榈诙似ヅ涫遣槐匾?，所以第三趟匹配是從i=2，j=0 開始，當(dāng)i=6，j=4 時(shí)匹配失敗。利用本趟部分匹配的結(jié)果：S[3]=T[1]且T[0]≠T[1]，S[4]=T[2]且T[0]≠T[2]，S[5]=T[3]且T[0]=T[3]，我們可以得到這樣的關(guān)系：S[3]≠T[0]，S[4]≠T[0]，S[5]=T[0]。

第四趟匹配：如果需要進(jìn)行，則應(yīng)該是從下標(biāo)i=3，j=0 開始，但是利用第三趟部分匹配的結(jié)果S[3]≠ T[0]，所以第四趟匹配也是沒有必要進(jìn)行的。

第五趟匹配：如果需要進(jìn)行，則應(yīng)該是從下標(biāo)i=4，j=0 開始，但是利用第三趟部分匹配的結(jié)果S[4]≠ T[0]，所以第五趟匹配也是沒有必要進(jìn)行的。

第六趟匹配： 這趟匹配本應(yīng)該從i=5，j=0 開始進(jìn)行，但是利用第三趟部分匹配的結(jié)果S[5]=T[0]，所以第6 趟匹配可以從i=6，j=1 時(shí)進(jìn)行，即從S[6]和T[1]開始進(jìn)行比較。當(dāng)i=10，j=5 時(shí)，模式T 中的全部字符都被比較完畢，所以模式匹配成功，此時(shí)應(yīng)該返回模式T 在主串S 中的位置序號6。

如果應(yīng)用模式匹配BF 算法對上述實(shí)例進(jìn)行匹配，需要進(jìn)行六趟匹配，而且每次匹配主串S 和模式T 都需要回溯，而通過上述實(shí)例分析我們可以看到，在這六趟匹配中，如果能夠充分利用第三趟部分匹配成功的結(jié)果，則第二、第四和第五這三趟匹配是沒有必要進(jìn)行的，所以總共只需要進(jìn)行三趟匹配就可以得到最終的匹配結(jié)果，這種模式匹配的過程也就是KMP 算法的中心思想。因此，KMP 算法的主要思想是：每當(dāng)某趟匹配失敗時(shí)，主串下標(biāo)不回溯，而是利用已經(jīng)得到的部分匹配的結(jié)果，將模式T向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。

所以現(xiàn)在的問題就是如何確定模式T 向右“滑動(dòng)”的距離，即：當(dāng)某趟匹配在S[i]和T[j]匹配失敗后，如何做到主串S 的下標(biāo)i 不回溯，而是根據(jù)當(dāng)前部分匹配結(jié)果，確定模式T 的下標(biāo)j 需要回溯到某個(gè)位置k，使得T[k]對準(zhǔn)S[i]繼續(xù)進(jìn)行比較。若主串S 和模式T 的某趟匹配在S[i]和T[j]匹配失敗后，j需回溯到位置k，那么根據(jù)當(dāng)前部分匹配結(jié)果，有以下等式成立：T[k-1]=S[i-1]、T[k-2]=S[i-2]、T[k-3]=S[i-3]……T[0]=S[i-k]，同時(shí)因?yàn)橄乱惶吮容^應(yīng)該從S[i]和T[k]開始，若此趟匹配中，S[i]和T[j]匹配失敗，那么在部分匹配成功時(shí)，我們又會有這樣的等式成立：T[j-1]=S[i-1]、T[j-2]=S[i-2]、T[j-3]=S[i-3]……T[j-k]=S[i-k]。綜合這些等式，我們可以得到：T[0]～ T[k-1]=T[j-k]～T[j-1]，這個(gè)等式說明：模式T 的下標(biāo)j 需要回溯到某個(gè)位置k 與j 具有函數(shù)關(guān)系，由當(dāng)前匹配失敗的位置j，可以計(jì)算出k 的值。

現(xiàn)在我們來看一下T[0]～ T[k-1]=T[j-k]～ T[j-1]代表的物理意義。T[0]～ T[k-1]表示以T[0]開頭的長度為k 的前綴子串，而T[j-k]～ T[j-1]表示以T[j-1]結(jié)尾的長度為k 的后綴子串。對于模式T=“ababac”，當(dāng)j=5時(shí)，因?yàn)門[0]=T[4]時(shí)，所以有k=1；又因?yàn)門[0]T[1]T[2]=T[2]T[3]T[4]，所以k=3。所以當(dāng)主串S 中的S[i]與模式T 中的T[j]不匹配時(shí)，需將S[i]與T[k]比較，此時(shí)選取k 的原則是：模式T 的前k 個(gè)字符子串等于T[j]之前的k 個(gè)字符子串，并且是具有此性質(zhì)的最大子串的串長，也就是max {k |1 ≤k ＜j 且T[0]… T[k-1]=T[j-k]… T[j-1]}。

在模式T=“t1t2…tm”中，因?yàn)樵赥的每一個(gè)位置都可能發(fā)生不匹配的情況，所以模式T 中的每個(gè)字符T[j](0 ≤j ＜m) 都有一個(gè)與之對應(yīng)k 值，而且這個(gè)k 值僅與模式T 本身有關(guān)而與主串S 無關(guān)(因?yàn)門[0]～ T[k-1]=T[j-k]～ T[j-1])。通常會定義next[j]函數(shù)來表示T[j](0 ≤j ＜m)對應(yīng)的k 值，也就是用一個(gè)數(shù)組next 來保存模式T 中的每一個(gè)字符T[j](0 ≤j ＜m)所對應(yīng)的k 值，通常next[j]函數(shù)的定義形式如下所示：

在next[j]函數(shù)的定義中next[j]=k 表示在匹配過程中當(dāng)S[i]!=T[j]時(shí)，下標(biāo)j 的回溯位置。通過next[j]函數(shù)求出模式T 的next 值后，KMP 算法的偽代碼描述如下所示：

算法：KMP

輸入：主串S，模式T，模式T 的next 值

輸出：T 在S 中的位置

1.設(shè)定S 和T 比較的開始下標(biāo)i=0，j=0；

2.重復(fù)2.1-2.3 中的操作，直到S 或T 的所有字符均被比較完畢：

（1）如果S[i]==T[j]，繼續(xù)比較S 和T 的下一對字符；

（2）否則，將j 回溯到next[j]位置，即j=next[j]；

（3）如果 j==-1，則i++，j++，準(zhǔn)備下一趟比較；

3.如果T 中所有字符均被比較完畢，則返回本趟匹配的開始位置；否則返回 0；

KMP 算法是一種經(jīng)典的模式匹配改進(jìn)算法，它消除了主串中下標(biāo)回溯的問題，因而提高了匹配的效率，但是僅當(dāng)模式與主串之間存在很多部分匹配情況下，KMP 算法那才能體現(xiàn)它的優(yōu)勢，否則和BF 模式匹配算法差別不大。