模式匹配KMP 算法思想分析

任憲臻 任美玲

(1.北京信息職業技術學院 軟件與信息學院，北京 100018；2.煙臺南山學院 工學院計算機系，山東 煙臺 265700)

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

圖1 主串S 和模式T

第一趟匹配：開始下標i=0，j=0，當i=2，j=2 時匹配失敗。利用本趟部分匹配的結果：S[1]=T[1]且T[0]≠T[1]，我們可以得到這樣的關系：S[1]≠ T[0]。

第二趟匹配：如果需要進行，則應該是從開始下標i=1，j=0 開始，但是利用第一趟匹配中得到的結果S[1]≠ T[0]，所以第二趟匹配是沒有必要進行的。

第三趟匹配：因為第二趟匹配是不必要的，所以第三趟匹配是從i=2，j=0 開始，當i=6，j=4 時匹配失敗。利用本趟部分匹配的結果：S[3]=T[1]且T[0]≠T[1]，S[4]=T[2]且T[0]≠T[2]，S[5]=T[3]且T[0]=T[3]，我們可以得到這樣的關系：S[3]≠T[0]，S[4]≠T[0]，S[5]=T[0]。

第四趟匹配：如果需要進行，則應該是從下標i=3，j=0 開始，但是利用第三趟部分匹配的結果S[3]≠ T[0]，所以第四趟匹配也是沒有必要進行的。

第五趟匹配：如果需要進行，則應該是從下標i=4，j=0 開始，但是利用第三趟部分匹配的結果S[4]≠ T[0]，所以第五趟匹配也是沒有必要進行的。

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

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

所以現在的問題就是如何確定模式T 向右“滑動”的距離，即：當某趟匹配在S[i]和T[j]匹配失敗后，如何做到主串S 的下標i 不回溯，而是根據當前部分匹配結果，確定模式T 的下標j 需要回溯到某個位置k，使得T[k]對準S[i]繼續進行比較。若主串S 和模式T 的某趟匹配在S[i]和T[j]匹配失敗后，j需回溯到位置k，那么根據當前部分匹配結果，有以下等式成立：T[k-1]=S[i-1]、T[k-2]=S[i-2]、T[k-3]=S[i-3]……T[0]=S[i-k]，同時因為下一趟比較應該從S[i]和T[k]開始，若此趟匹配中，S[i]和T[j]匹配失敗，那么在部分匹配成功時，我們又會有這樣的等式成立：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]，這個等式說明：模式T 的下標j 需要回溯到某個位置k 與j 具有函數關系，由當前匹配失敗的位置j，可以計算出k 的值。

現在我們來看一下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]結尾的長度為k 的后綴子串。對于模式T=“ababac”，當j=5時，因為T[0]=T[4]時，所以有k=1；又因為T[0]T[1]T[2]=T[2]T[3]T[4]，所以k=3。所以當主串S 中的S[i]與模式T 中的T[j]不匹配時，需將S[i]與T[k]比較，此時選取k 的原則是：模式T 的前k 個字符子串等于T[j]之前的k 個字符子串，并且是具有此性質的最大子串的串長，也就是max {k |1 ≤k ＜j 且T[0]… T[k-1]=T[j-k]… T[j-1]}。

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

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

算法：KMP

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

輸出：T 在S 中的位置

1.設定S 和T 比較的開始下標i=0，j=0；

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

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

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

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

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

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