維基百科

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

建立表的算法的效率

建立表的算法的複雜度是 ，其中 是W的長度。

除去一些初始化的工作，所有工作都在循環中完成。為說明循環執行用了 的時間，考慮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時終止，此循環必然在最多 次迭代後終止。因此建立表的算法的複雜度是 。

另見

外部連結

引用

取自「https://zh.wikipedia.org/w/index.php?title=KMP算法&oldid=81777252」