白话 KMP 算法

来源：情诗网 2020-11-27 分类：表白情话

KMP 算法是计算机字符串匹配的常规算法。wiki
本篇文章借助简单示例，用通俗易懂的方式描述对 KMP 算法的理解。

匹配值表

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

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

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

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

字符串	前缀集合	后缀集合	前缀后缀交集
"A"	[]	[]	[]
"AB"	[A]	[B]	[]
"ABA"	[A,AB]	[A, BA]	[A]
"ABAB"	[A, AB, ABA]	[B, AB, BAB]	[AB]
"ABABA"	[A, AB, ABA, ABAB]	[A, BA, ABA, BABA]	[A, ABA]
"ABABAB"	[A, AB, ABA, ABAB, ABABA]	[B, AB, BAB, ABAB, BABAB]	[AB, ABAB]
"ABABABC"	[A, AB, ABA, ABAB, ABABA, ABABAB]	[C, BC, ABC, BABC, ABABC, BABABC]	[]
"ABABABCA"	[A, AB, ABA, ABAB, ABABA, ABABAB, ABABABC]	[A, CA, BCA, ABCA, BABCA, ABABCA, BABABCA]	[A]

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

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

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

那么不难从上表中得出每一位(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)，找到了最终匹配结果。