KMP演算法

在本文中，將使用始於零的陣列來表示字串。比如，若字串S = "ABC"，則S[2]表示字元'C'。這種表示方法與C語言一致。

在電腦科學中，克努斯-莫里斯-普拉特字串尋找演算法（英語：Knuth–Morris–Pratt algorithm，簡稱為KMP演算法）可在一個字串S內尋找一個字W的出現位置。一個詞在不匹配時本身就包含足夠的資訊來確定下一個匹配可能的開始位置，此演算法利用這一特性以避免重新檢查先前配對的字元。

這個演算法由高德納和沃恩·普拉特在1974年構思，同年詹姆斯·H·莫里斯也獨立地設計出該演算法，最終三人於1977年聯合發表。

尋找過程[編輯]

以W="ABCDABD"，S="ABC ABCDAB ABCDABCDABDE"為例說明尋找過程。尋找過程同時使用兩個迴圈變數m和i：

m代表主文字串S內匹配字串W的當前尋找位置，
i代表匹配字串W當前做比較的字元位置。

圖示如下：

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

從W與S的開頭比較起。比對到S[3](=' ')時，發現W[3](='D')與之不符。接着並不是從S[1]比較下去。已經知道S[1]~S[3]不與W[0]相合。因此，略過這些字元，令m = 4以及i = 0。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

如上所示，檢核了"ABCDAB"這個字串。然而，下一字元便不相合。可以注意到，"AB"在"ABCDAB"的頭尾處均有出現。這意味着尾端的"AB"可以作為下次比較的起始點。因此，令m = 8, i = 2，繼續比較。圖示如下：

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

於m = 10的地方，又出現不相符的情況。類似地，令m = 11, i = 0繼續比較：

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

這時，S[17](='C')不與W[6]相同，但是已匹配部分"ABCDAB"亦為首尾均有"AB"，採取一貫的作法，令m = 15和i = 2，繼續搜尋。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

找到完全匹配的字串了，其起始位置於S[15]的地方。

部分匹配表[編輯]

部分匹配表，又稱為失配函數，作用是讓演算法無需多次匹配S中的任何字元。能夠實現線性時間搜尋的關鍵是在主串的一些欄位中檢查模式串的初始欄位，可以確切地知道在當前位置之前的一個潛在匹配的位置。換句話說，在不錯過任何潛在匹配的情況下，"預搜尋"這個模式串本身並將其譯成一個包含所有可能失配的位置對應可以繞過最多無效字元的列表。

對於W中的任何位置，都希望能夠查詢那個位置前（不包括那個位置）有可能的W的最長初始欄位的長度，而不是重新從W[0]開始比較整個欄位，這長度就是尋找下一個匹配時回退的距離。因此T[i]是W的可能的適當初始欄位同時也是結束於W[i - 1]的子串的最大長度。使空字串長度是0。當一個失配出現在模式串的最開始，這是特殊情況（無法回退），設置T[0] = -1，在下面討論。

建立表演算法範例[編輯]

以W = "ABCDABD"為例。以下將看到，部分匹配表的生成過程與前述尋找過程大同小異，且出於類似原因是高效的。

首先，設定T[0] = -1。為求出T[1]，必須找到一個"A"的真字尾（真字尾指不等於原串的字尾）兼W的字首。但"A"沒有真字尾，所以設定T[1] = 0。類似地，T[2] = 0。

繼續到T[3]，注意到檢查所有字尾有一個捷徑：假設存在符合條件的前字尾，兩者分別為W[0..1] = W[1..2]，則必有W[0..0] = W[1..1]。由於W[0..0]亦是W的真字首，上一步必然已經得到T[2] = 1（而有T[2] = 0，說明假設不成立）。一般地，遍歷到每個字元時，只有上一步已經發現一個長為m的有效字尾，才需要判斷有無長為m+1的字尾，而毋需考慮長為m+2、m+3等的字尾。

從而，不必考慮長為2的字尾，而唯獨需要考慮的長度1亦不可行，故得到T[3]=0。

接下來是W[4] = 'A'。基於同樣的理由，需要考慮的最大長度為1，並且在'A'這個情況中有效，回退到尋找的當前字元之前的欄位，因此T[4] = 0。

現在考慮下一個字元W[5] = 'B'，使用這樣的邏輯：如果曾發現一個子模式在上一個字元W[4]之前出現，繼續到當前字元W[5]，那麼在它之前它本身會擁有一個結束於W[4]合適的初始段，與事實相反的是已經找到'A'是最早出現在結束於W[4]的合適欄位。因此為了找到W[5]的終止串，不需要檢視W[4]。因此T[5] = 1。

最後到W[4] = 'A'。下一個字元是'B'，並且這也確實是W[5]。此外，上面的相同參數說明為了尋找W[6]的欄位，不需要向前檢視W[4]，所以得出T[6] = 2。

於是得到下面的表：

`i`	0	1	2	3	4	5	6
`W[i]`	A	B	C	D	A	B	D
`T[i]`	-1	0	0	0	1	2	0

另一個更複雜和有趣的例子：

`i`	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
`W[i]`	P	A	R	T	I	C	I	P	A	T	E		I	N		P	A	R	A	C	H	U	T	E
`T[i]`	-1	0	0	0	0	0	0	1	2	0	0	0	0	0	0	1	2	3	0	0	0	0	0	0

建立表演算法的偽代碼的解釋[編輯]

上面的例子以最少的複雜步驟展示了組織這個表格的一般性方法。這麼做的原理是對整體的搜尋：大多數工作已經在檢測到當前位置的時候做完了，剩下需要做的很少。略微複雜的一點是找到一個共同前字尾。這就需要有一些初始化的代碼。

algorithm kmp_table:
    input:
        an array of characters, W (the word to be analyzed)
        an array of integers, T (the table to be filled)
    output:
        nothing (but during operation, it populates the table)

    define variables:
        an integer, pos ← 2 (the current position we are computing in T)
        an integer, cnd ← 0 (the zero-based index in W of the next 
character of the current candidate substring)

    (the first few values are fixed but different from what the algorithm 
might suggest)
    let T[0] ← -1, T[1] ← 0

    while pos < length(W) do
        (first case: the substring continues)
        if W[pos - 1] = W[cnd] then
            let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (second case: it doesn't, but we can fall back)
        else if cnd > 0 then
            let cnd ← T[cnd]

        (third case: we have run out of candidates.  Note cnd = 0)
        else
            let T[pos] ← 0, pos ← pos + 1

建立表的演算法的效率[編輯]

建立表的演算法的複雜度是 $O(n)$ ，其中 $n$ 是W的長度。

除去一些初始化的工作，所有工作都在迴圈中完成。為說明迴圈執行用了 $O(n)$ 的時間，考慮pos和pos - cnd的大小。

在第一個分支里，pos - cnd不變，而pos與cnd同時自增，自然，pos增加了。
在第二個分支里，cnd被更小的T[cnd]所替代，從而增加了pos - cnd。
在第三個分支里，pos增加了，而cnd不變，所以pos和pos - cnd都增加了。

因為pos ≥ pos - cnd，即在每一個階段要麼pos增加，要麼pos的一個下界增加。故既然演算法在pos = n時終止，此迴圈必然在最多 $2n$ 次迭代後終止。因此建立表的演算法的複雜度是 $O(n)$ 。

另見[編輯]

Boyer-Moore字串搜尋演算法

外部連結[編輯]

（英文）An explanation of the algorithm （頁面存檔備份，存於互聯網檔案館） and sample C++ code （頁面存檔備份，存於互聯網檔案館） by David Eppstein
（英文）Knuth-Morris-Pratt algorithm （頁面存檔備份，存於互聯網檔案館） description and C code by Christian Charras and Thierry Lecroq
（英文）Interactive animation for Knuth-Morris-Pratt algorithm by Mike Goodrich
（英文）Explanation of the algorithm from scratch （頁面存檔備份，存於互聯網檔案館） by FH Flensburg.

參照[編輯]

高德納; James H. Morris, Jr, Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing. 1977, 6 (2): 323–350 [2006-07-27]. （原始內容存檔於2010-01-04）.

Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Section 32.4: The Knuth-Morris-Pratt algorithm. Introduction to Algorithms Second edition. MIT Press and McGraw-Hill. 2001: 923-931. ISBN 978-0-262-03293-3.