JS KMP Matcher

简单的 KMP 算法（即 Knuth–Morris–Pratt 算法）的实现，用于学习之目的，代码当中有每一部分的详细说明。

算法简介

KMP 是一种字符串搜索算法。字符串搜索是指在 目标字符串 里搜索指定 关键字 所出现的位置，比如在各种文本编辑器里使用 "查找" 功能就是字符串搜索。

简单思想

1. KMP 算法假设 关键字 字符串里的 子字符串（指从第一个字符开始到中间任意位置的一部分字符串）存在头尾相同的一个或多个字符的情况；
2. 在暴力搜索（Brute-force search）的基础上，每当遇到字符不匹配的时候，则检查已匹配的部分有无存在 头尾相同的字符，有的话则跳过相同的字符。

示例：

start--v     v--i
.......aiiiiabcd.....  <-- 目标字符串
       aiiiiaz         <-- 关键字字符串
             ^--j

在上图中，当轮匹配从第一个字符 a 开始，然后比较每一个 i 和 j 位置的字符，匹配则同时推进 i 和 j 指针，当推进到字符 b 时，发现字符不匹配。对于暴力搜索，这时会把 i 指针回退到 start + 1，j 回退到 0，然后开始新一轮匹配。

但 KMP 并不回退 i，它会通过一个事先创建好的 "关键字部分匹配表" 查找已匹配部分，即 aiiiia 有无头尾相同的字符，在当前这个例子里是存在的，相同的字符是 a，所以只需把关键字字符串右移 5 个字符位置，让 头 a 对齐 尾 a，（注，让关键字右移，实际上就是减少 j 的值，在这个例子里，j 要减去 5），然后从刚才停下来的位置开始继续匹配。

KMP 之所以能够如此 "大胆" 跳过 4 个字符，是因为它（通过查表）知道在头尾 a 字符之间不会再出现 a，所以比较这段字符串毫无意义。这时不妨想象一下对于暴力搜索，它会用关键字的第一个字符 a 去逐个比较目标字符串里的 iiiia，显然前面的 4 个 i 比较毫无必要。

下面是一个 头尾相同字符 由多个字符组成的例子：

start--v         v--i
.......abcabababcxyzdef.....  <-- 目标字符串
       abcabababci            <-- 关键字字符串
                 ^--j

在上图中，当匹配到字符 x 时，发现不匹配。而已匹配的部分，即 abcabababc 存在头尾相同的字符 abc，所以这时只需把关键字右移 7 个字符位置，让 头 abc 对齐 尾 abc，（即让 j 减去 7），然后从刚才停下来的位置开始继续匹配。

从上面的原理可知，KMP 加速的关键在于 关键字字符串 里存在重复的字符，对于小字符集（比如英文字母）或者更小的字符集会有比较良好的效果，但对于大字符集（比如中文）效果不明显，极端情况下如果 关键字字符串 里不存在任何重复的字符，实际上仍然是暴力搜索，而且还会多一个建表和查表过程，速度会比暴力搜索更慢。

建立 "关键字部分匹配表" 的方法

"关键字部分匹配表" 也就是关键字各子字符串的 "头尾相同的字符表"，或者说 "最大公共前后缀表"。

假设关键子字符串是 "abcdabd"，则 "关键字部分匹配表" 如下：

| 子字符串 | 头尾相同的字符 | 长度 | |---------|---------------|---------| | a | 单个字符不存在 | 0 | | ab | 无 | 0 | | abc | 无 | 0 | | abcd | 无 | 0 | | abcda | a | 1 | | abcdab | ab | 2 | | abcdabd | 无 | 0 |

用程序建立 "关键字部分匹配表" 的过程跟搜索过程一样，同样可以用暴力搜索法来创建，也可以用在建立过程中形成的 半成品表 来一次迷你的 KMP 搜索。

这个过程单纯用语言描述比较模糊，下面的是河马蜀黍自己乱想出来的实物演示法😅，动手做一下可以很快发现规律：

准备一条纸条，宽度为 1cm，长度为关键字字符的长度（即 length cm），然后每一格（cm）填上一个字母。这时这条纸条就是关键字字符数组。

关键字可以参考下面几个有代表性的：

• 'abaab'
• 'aaaab'
• 'aabaaa'
• 'abcdabd'

复制一条一模一样的纸条。

将两条纸条一上一下平铺，然后左右错开一格，再逐渐拉开，每次拉开一格，直到只剩下还连着一格为止，在拉开的过程中找到上下两条纸条内容重叠/相同的位置，这个重叠的长度就是 "最大公共前后缀长度"。

然后折掉最右边一格，重复上面的步骤，找到长度为 length - 1 时的 "最大公共前后缀长度"。

不断折掉最右边的一格，直到只剩下 2 格为止，找到所有长度下的 "最大公共前后缀长度"。（因为 1 个字符不存在前缀或后缀，所以不需要减到 1 个字符）。

实际计算时并不需要重复计算每一种长度的情况，只需计算一次最长的长度即可，因为由上面的演示可见，不同长度的前面的步骤都是 一模一样 的。

程序的过程如下：

如果 i （上纸条当前比较的字符的位置） 和 j （下纸条当前比较字符的位置） 的字符：
1. 不同：
   a. 如果 j == 0，则 i++
   b. 如果 j != 0, 有两种方式：
      I.  暴力搜索法：
          将 i 退回到第 i-j+1，即 i 和 j 第一次相同的后一个字符；
          将 j 退回到 0。
      II. 现做现用迷你 KMP 法，因为目前 table （尽管还不完整）已经记录了部分头尾相同的子字符串，
          j 不需要退回到 0，只需要将 j 退回到 table[j-1] 即可，即跳过头尾相同字符中间的那些必然不会匹配的字符。
          i 保持不变。
2. 相同：则 i++, j++

在计算过程中，j 的值就是关键字子字符串长度为 i 时的 "最大公共前后缀长度" 。

单元测试

执行命令：

$ npm test

应该能看到 testKMP() passed. 字样。

单步调试/跟踪

有时可能跟踪程序的运行也能帮助对程序的理解，启动单步调试的方法是：

在 vscode 里打开该项目，然后在单元测试文件 test-all.js 或者源码 kmp.js 里设置断点，然后执行 Run and Debug 即可。

字符串搜索算法系列项目

• JS Rabin-Karp Matcher https://github.com/hemashushu/js-rabin-karp-matcher

• JS Boyer-Moore-Horspool Matcher https://github.com/hemashushu/js-boyer-moore-horspool-matcher

• JS KMP Matcher https://github.com/hemashushu/js-kmp-matcher

• JS Aho-Corasick Matcher https://github.com/hemashushu/js-aho-corasick-matcher

• JS Regexp Interpreter https://github.com/hemashushu/js-regexp-interpreter