KMP算法

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

在電腦科學中，**Knuth-Morris-Pratt 字串尋找演算法**（簡稱為 **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`。

於是得到下面的表：

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

### 建立表演算法的虛擬碼的解釋

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

```
**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.  引文格式 1 維護：冗餘文字 (link)