白话 KMP 算法

KMP 算法是计算机字符串匹配的常规算法。wiki

本篇文章借助简单示例，用通俗易懂的方式描述对 KMP 算法的理解。

匹配值表

对于 KMP 来说，“匹配值表”是很关键的。下面我们从简单示例出发描述匹配值表是如何产生的，以便理解。

现在 我们需要查找的字符串是 “ABABABCA”。

在描述“匹配值表“之前，我们需要简短的介绍下前缀和后缀的概念:

前缀：从 0 位，依次截取 1 到(len - 1)长度字符串的集合

后缀：从 len - 1 位反序，依次截取 1 到(len - 1)长度字符串的集合

从上表，如果耐心看，完全可以理解前缀和后缀的概念。

那么“匹配值”又是指什么呢？

“匹配值”是指前缀和后缀集合，最长共有元素的长度，即交集中最长元素的长度

那么不难从上表中得出每一位(index)字符对应“匹配值(value)”:

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 |
复制代码

匹配值表的使用

我们可以根据匹配值表来加速查找匹配的过程。

下面还是举例说明问题：

在字符串"BACBABABAABCBABABABCA"(text)中查找上文中的字符串"ABABABCA"(pattern)， 下文中对两个字符串的代称为括号之内的单词。

从 text 第一位开始匹配，第一次匹配成功是这样：

BACBABABAABCBABABABCA
 |
 ABABABCA
复制代码

那么开始往后匹配，发现 text 的第二位"C"和 pattern 的第二位"B"不匹配， 所以当前部分匹配长度为1(只有一个A)，并且根据上文的匹配值表得到，当前的匹配值为 0。

移动位数 = 已匹配字符长度 - 对应位的匹配值

即 移动位数 = 1 - 0，所以我们继续向后移一位进行匹配。

再一次匹配成功的情形：

BACBABABAABCBABABABCA
    |||||
    ABABABCA
复制代码

此时，text 中的"A"与 pattern 中的 "B" 不匹配，如果不按照算法，肯定是继续后移一位进行匹配。 如果根据上述计算公式：

移动位数 = "ABABA".length - pattern[4]的匹配值

即 5 - 3 = 2

所以我们可以一次后移两位：

BACBABABAABCBABABABCA
    xx|||
      ABABABCA
复制代码

又不匹配了，此时应该后移

"ABA".length - pattern[2]的匹配值

即 3 - 1 = 2

继续后移两位：

BACBABABAABCBABABABCA
      xx|
        ABABABCA
复制代码

继续后移

"A".length - pattern[0]的匹配值

即 1 - 0 = 1

后移一位：

BACBABABAABCBABABABCA
        x||
         ABABABCA
复制代码

继续后移

"AB".length - pattern[1]的匹配值

即 2 - 0 = 2

后移两位：

BACBABABAABCBABABABCA
         xx|
           ABABABCA
复制代码

第一位都不匹配，我们继续往后移动直到匹配成功

BACBABABAABCBABABABCA
             ||||||||
             ABABABCA
复制代码

移动几次之后(step=1)，找到了最终匹配结果。

参考： jakeboxer.com/blog/2009/1…