克努斯-莫里斯-普拉特算法

Knuth-Morris-Pratt 字符串查找算法（常简称为 “KMP算法”）是在一个“主文本字符串” S 内查找一个“词” W 的出现，通过观察发现，在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始，以此避免对以前匹配过的字符重新检查。

这个算法是由高德纳（Donald Ervin Knuth）和 沃恩·普拉特 在1977年合作发明的，同年詹姆斯·H·莫里斯也独立地设计出该算法，但是最终由三人联合发表。

注意： 在本文中，我们将使用始于零的数组来表示我们的字符串；所以下面例子中 W 中的 'C' 将被表示为 W[2]。一般来说，表示法服从 C 语法。

算法说明

查找算法实例

让我们用一个实例来演示这个算法。在任意给定时间，本算法被两个整数 m 和 i 所决定： m 代表主文字符串S 内匹配字符串 W 的当前查找位置；i 代表匹配字符串W当前做比较的字符位置。图示如下：

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。

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

如上所示，我們檢核了 "ABCDAB" 這個字串。然而，這與目標仍有些差異。我們可以注意到，"AB"在字串頭尾處出現了兩次。這意味著尾端的 "AB" 可以作為下次比較的起始點。因此，我們令 m = 8, i = 2，繼續比較。圖示如下：

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

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

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

這時，S[17](='C') 不與 W[6]相同，但是亦出現了兩次 "AB"，我們採取一貫的作法，令 m = 15 和 i = 2 ，繼續搜尋。

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

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

外部連結

• （中文）从头到尾理解KMP算法 by saturnman
• （中文）KMP算法详解 by Matrix67
• （英文）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. 

• 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 0-262-03293-7.