KMP 算法

转载自：字符串匹配的 KMP 算法

KMP 算法以三个发明者命名，K 表示著名科学家 Donald Knuth。

KMP 算法用于在字符串中快速找到搜索词。

举例

设字符串为 BBC ABCDAB ABCDABCDABDE，我想找到搜索词为 ABCDABD。

搜索词的匹配过程中，会遇到如下情况：

BBC ABCDAB ABCDABCDABDE
    ABCDABD

此时 D 和空格不匹配，如果是常规思路，我们会将搜索词往后移，然后继续匹配。

BBC ABCDAB ABCDABCDABDE
     ABCDABD

但其实我们可以利用已知信息简化。

部分匹配表的使用

针对搜索词 ABCDABD，我们做出它的部分匹配表：

至于这张表是如何产生的，后面会介绍。

移动位数

在计算过程中，会遇到如下情况：

BBC ABCDAB ABCDABCDABDE
    ABCDABD

已知空格与 D 不匹配时，前面六个字符 ABCDAB 是匹配的。查表可知，最后一个匹配字符 B 对应的部分匹配值为 2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于 4，所以将搜索词向后移动 4 位。

BBC ABCDAB ABCDABCDABDE
        ABCDABD

因为空格与 Ｃ 不匹配，搜索词还要继续往后移。这时，已匹配的字符数为 2（AB），对应的部分匹配值为 0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位。

BBC ABCDAB ABCDABCDABDE
          ABCDABD

因为空格与 A 不匹配，继续后移一位。

BBC ABCDAB ABCDABCDABDE
           ABCDABD

逐位比较，直到发现 C 与 D 不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位。

BBC ABCDAB ABCDABCDABDE
               ABCDABD

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了。

部分匹配表的生成

部分匹配值就是前缀和后缀的最长的共有元素的长度。以 ABCDABD 为例：

• A 的前缀和后缀都为空集，共有元素的长度为 0
• AB 的前缀和后缀无交集，共有元素的长度为 0
• ABCDA 的前缀和后缀的共有最长元素为 A，长度为 1
• ABCDAB 的前缀和后缀的共有最长元素为 AB，长度为 2

部分匹配的实质是，有时候，字符串头部和尾部会有重复。比如 ABCDAB，第一个 AB 向后移动 4 位（字符串长度 - 部分匹配值），就可以来到第二个 AB 的位置。