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: ABCABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
```

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

```
1         2
m: 01234567890123456789012
S: ABCABCDAB ABCDABCDABDE
W:    ABCDABD
i:    0123456
```

可以看出，第一位`W[0](='A')`直接不匹配`S[3](=' ')`，因此往後移動一位至`m = 4`繼續與`i = 0`進行比較。

```
1         2
m: 01234567890123456789012
S: ABC ABCDABABCDABCDABDE
W:     ABCDABD
i:     0123456
```

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

```
1         2
m: 01234567890123456789012
S: ABC ABCDABABCDABCDABDE
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｜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｜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 <br>character of the current candidate substring)

    (the first few values are fixed but different from what the algorithm <br>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)$。

## 外部連結

- 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.