在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（常简称为“KMP算法”）可在一个主“文本字符串”S内查找一个“词”W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。（from wikipedia）

关于KMP算法的实现思想，官方的解释较为复杂，这里我给出一个较为简单的解释，至于KMP算法为什么比朴素的字符串匹配算法更有效率，在很多算法书中已经解释得够好了，我就不赘述了。

先介绍一个关键的东西：“The Partial Match Table” （部分匹配表），这是KMP算法的精华所在。

想必理解这个算法的主要障碍就是部分匹配表中的这些数字究竟意味着什么，我现在试着用比较简单的话来解释它们。

以下是字符串 “abababca” 的部分匹配表：

1
2
3
char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

如果有一个八个字符的字符串 “abababca” ，我的部分匹配表将有八个单元格。如果我们正在看表中的第八个（最后一个）单元格，那么我们对整个字符串 “abababca” 感兴趣 。如果我们正在看表格中的第七个单元格，那么我们对字符串中的前七个字符 “abababc” 感兴趣，即第八个 “a” 是不相关的，可以无视它，依此类推。

现在，我们需要知道什么是“正确前缀（Proper prefix）”和“正确后缀（Proper suffix）”。

正确前缀：一个字符串尾部截去一个或多个字符形成的子串。

“S”, “Su”, “Sus”和”Sush”都是”Sushi”的正确的前缀。

正确后缀：一个字符串头部截去一个或多个字符形成的子串。

“ashimi”, “shimi”, “himi”, “imi”, “mi”, “i”都是“Sashimi”的正确后缀。

考虑到这一点，我们现在可以给部分匹配表中的 “value” 下一个定义：

“部分匹配值（value）”就是“正确前缀”和“正确后缀”的最长的共有元素的长度。

下面来举几个例子。

比如我们正在看第三个单元格。正如之前所说，我们只对前三个字符（”aba”）感兴趣。在”aba”中，有两个正确前缀（”a”和”ab”）和两个正确后缀（”a”和”ba”）。显然，这两个集合中的公共元素是”a”。因此，在这种情况下，“正确前缀”和“正确后缀”的最长的共有元素的长度为1，即单元格三的value为1。

我们来试试第四个单元格。在这里，我们对前四个字符（”abab”）感兴趣。我们有三个正确前缀（”a”, “ab”和”aba”）和三个正确后缀（”b”, “ab”和”bab”）。这一次，公共元素”ab”长度为2，所以单元格四的value为2。

至于第五个单元格，前五个字符为“ababa”。我们有四个正确前缀（”a”, “ab”, “aba”和”abab”）和四个正确后缀（”a”, “ba”, “aba”和”baba”）。现在我们有两个公共元素：”a”和”aba”，由于”aba”比”a”长，因此获胜，单元格五的value为3。

我们跳到单元格七，前七个字符为”abababc”。即使没有列举所有正确前缀和正确后缀，很明显，不会有任何公共元素：所有正确后缀将以”c”字母结尾，并且所有正确前缀都不会以”c”结尾。所以单元格七的value为0。

最后，我们来看看第八个单元格，它关注整个字符串”abababca”。由于它们以”a”开头和结尾，所以我们知道value至少为1。长度为1以上的子串中，所有正确后缀都包含”c”，而只有最后一个正确前缀”abababc”包含”c”。这个七个字符的正确前缀与七个字符的正确后缀”bababca”不匹配，所以单元格八的value为1。

接下来介绍一下如何使用“部分匹配表”

当我们找到部分匹配（无法完全匹配）时，我们可以使用部分匹配表中的值来跳过一些字符（而不是重做一些不必要的旧比较）。公式如下：

移动位数 = 已匹配的字符数(m) - 对应的部分匹配值(value[m-1])

假设我们将字符串“abababca”与被比较字符串“bacbababaababbbb”相匹配，这是我们的部分匹配表，方便参考:

1
2
3
char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

第一次我们在这里遇到了部分匹配：

1
2
3
bacbababaabcbab
 |
 abababca

我们注意到已匹配的字符数为1，而对应的部分匹配值为value[1-1] = 0，根据公式得到移动位数为1，也就是说无需跳过。

接下来我们得到的部分匹配是在这里：

1
2
3
bacbababaabcbab
    |||||
    abababca

我们注意到已匹配的字符数为5，而对应的部分匹配值为value[5-1] = 3，根据公式得到移动位数为2，即：

1
2
3
4
5
// x 代表移动的位数

bacbababaabcbab
    xx|||
      abababca

这时已匹配的字符数为3，而对应的部分匹配值为value[3-1] = 1，根据公式得到移动位数为2，即：

1
2
3
4
5
// x 代表移动的位数

bacbababaabcbab
      xx|
        abababca

此时，我们的字符串已经比被比较字符串要长了，所以我们知道没有匹配。

总结

就像我之前说的那样，这篇文章不是KMP算法的证明或者是详尽的解释，只是帮助刚接触KMP算法的同学们能够更轻松地理解KMP算法是如何实现的。如果有更好的解释，欢迎联系。