JavaScript 算法 KMP（Knuth-Morris-Pratt ） 算法

Question

KMP 是著名的字符串匹配算法，效率高但比较难理解（一看就懂的请勿代入）。

字符串匹配问题是指从一段已有的文本串（记为 txt，长度记为 N）中匹配模式串（记为 pat，长度记为 M），我们首先从暴力匹配算法开始，讲一讲为什么会有 KMP（KMP是为解决什么问题）。

暴力匹配

function directSearch(pat, txt) {
    if (!pat || !txt) return -1;

    const txtLen = txt.length;
    const patLen = pat.length;

    for (let i = 0; i < txtLen - patLen + 1; i++) {
        let j;
        for (j = 0; j < patLen; j++) {
            if (pat[j] !== txt[i + j]) {
                break;
            }
        }
        // j 等于 patLen，代表比较过程全部走完，即全部匹配
        if (j === patLen) {
            return i;
        }
    }
    return -1;
}

如上，暴力匹配即从文本串第一位开始，每次都遍历整个模式串来一一比较，简单直接，时间复杂度为 O(MN)。

但暴力匹配有个问题：它不够智能，每次都需要从头开始重新一一比较，之前比较过程中匹配的部分没法利用，做了很多无用功。那么有没有方法可以利用之前比较的结果？有，这就是KMP。

从 PMT （部分匹配表 Partial Match Table）开始来理解 KMP

这里为什么不从 KMP 的概念开始学习 KMP（正如我们以前学习一般算法那样）？因为从概念开始，最后讲到 PMT 真的不容易理解，所以干脆反其道而行之，先来理解 KMP 的核心概念：部分匹配表PMT。

1) 字符串的前缀、后缀到 PMT

理解PMT的前置要求就是理解字符串的前缀、后缀。假设字符串 A、B、S，存在 A=BS，其中 S 是任意的非空字符串，那就称B为A的前缀。后缀同理。

PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

举例描述，对 aba 而言，前缀是 {a, ab}，后缀是 {ba, a}，那么交集就是 {a}，PMT中对应值就是 1。

假设模式串 pat 是 abababca，那么对应的 PMT 表就是：

char:	a	b	a	b	a	b	c	a
index:	0	1	2	3	4	5	6	7
value:	0	0	1 (a)	2 (ab)	3 (aba)	4 (abab)	0	1 (a)

2) PMT可以帮助到暴力匹配什么

现在我们已经有了 PMT 了，那它可以用来优化暴力匹配吗？当然可以，这里也就是 KMP 理解的难点。

暴力匹配被认为效率低的地方在于一旦不匹配，就只能从头开始比较，之前的比较结果无法利用。但当我们有了 PMT ，我们就再也不用从头比较了！

我们尝试来在暴力匹配中加入 PMT ：

txt: ababababca -- i 是遍历 txt 的下标
pat: abababca --j 是遍历 pat 的下标

1. 暴力匹配第一轮在碰到 c 的时候，即 i = j = 6 时，发现了不匹配；
2. 如果没有 PMT，那么我们之能重置i = 1, j = 0开始重新比较（这里就是为什么低效，i 要回头，然后比较整个 pat）；
3. 但是借助 PMT，我们可以不用让 i 回头，我们保持 i = 6, 设置 j = 5，继续比较。

如上就是借助 PMT 之后的比较过程（即KMP），它可以保证 i 不回退，可以尽量不重新比较整个模式串（j 设置为合理的值而不像暴力匹配那样直接重置为 0）。

但为什么可以比暴力匹配更聪明？即为什么 i 不回退， j 是 5？

1. 初始化 i = j = 0 开始匹配，直到 i = j = 6 不匹配。
2. 我们的目的是希望文本串（txt）只循环一遍，即 i 不回退，这就是为什么 i 保持 6 不变。我们需要解释的是 i 不变可以保证匹配正确性吗（即正确的匹配结果肯定不是 i 为 1- 5）？由第4点解释。
3. 当 i = j = 6 （第7位）不匹配时，暗含的是之前6位（0-5，ababab）是相同的，即模式串（pat）和文本串（txt） 均包含相同的子串 ababab，又因为 i 不变，那么找到合适的 j 继续比较其实就是找 ababab 的前缀、后缀的交集的最大长度——恰好这个工作已经由我们的 PMT 先做了，我们查到 index 为 5 对应的值是 4，那么 j 就是 4 （下标为4，前4位是 abab，作为ababab的前缀，同时以文本串的角度而言，是后缀）。

   再详细一点来解释一下。因为 i 不变（这是设定，为什么可以这样设定第4点解释），所以我们相当于是把模式串 pat 向后移动，对模式串和文本串共有的 ababab 而言，是不是就是找到 ababab 的前缀、后缀的交集的最大长度？很直接吧。

4. 好了，这一步来解释一下为什么 i 可以保持不变。如上一步而言，当 i = j = 6 （第7位）不匹配时，前 6 位（ababab）是匹配的。假设我们用暴力匹配的方法，把 i 设置为 1，j 设置为 0 开始重新比较，有没有发现，对 i 从 1 到 5 而言（即 j 从 0 到 4），我们仍然是在比较 ababab 的前缀后缀？！
   • 对 i = 1，我们是在问 ababab 是不是有最大长度 5 的前缀后缀交集，即 PMT 表的值有没有 5，并没有；
   • 对于 i = 2，我们是在问 ababab 的 PMT 表值是不是有 4，真的有；有没有发现这时候字符串的位置和我们第 3 步得到的是一样的？
   • 其实正因为对 1 - 5 的暴力匹配过程本质上就是在查询 PMT 表，所以我们可以直接设定 i 不变，找到对应的 j 即可！
5. 至此，KMP 的核心思想应该可以理解了，即 PMT 表简化/消除了在部分匹配时暴力匹配的重复工作，暴力匹配在部分匹配的情况下本质是在找某一字符串的前缀、后缀的最长交集。

KMP 的实现

function getPMT(pat) {
    const next = Array(pat.length).fill(-1);

    let i = 0;
    let j = -1;
    // next[0] = -1, next[1] = 0 为固定值；真正的计算从 i = 2 开始；
    while (i < pat.length) {
        if (j === -1 || pat[i] === pat[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }

    return next;
}

function kmpSearch(txt, pat) {
    let i = 0;
    let j = 0;
    const next = getPMT(pat);
    while (i < txt.length && j < pat.length) {
        if (j == -1 || txt[i] === pat[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j === pat.length) {
        return i - j;
    }
    return -1;
}