KMP字符串匹配算法

算法分析

Knuth-Morris-Pratt（KMP）算法是一种改进的字符串匹配算法，核心是利用匹配失败后的信息，减少pattern串和主串的匹配次数以达到快速匹配的目的。

时间复杂度是 O(m+n)

例子

例如有字符串 S 和 P，判断模式串 P 是否是 S 的子串：

按照普通的匹配方式，设 P 串开始匹配的位置是 i，S 串开始匹配的位置是 j：

1. 从 i = 0 开始匹配，到 i = j = 2 时，发现了 A 和 T 不匹配，于是我们把 j 往后移一位，从 j = 1, i = 0 开始重新匹配；
2. 发现 C 不匹配 A，把 j 往后移一位，从 j = 2, i = 0 开始重新匹配；
3. 重复上述两个步骤，直到 j = 9, i = 0，匹配到 j = 16, i = 7 结束。

在每一轮匹配时，需要重复对 P 串的 AC 进行比较，并且前面的 AC 越多，浪费的时间就越多。
假设 S 的长度为 m，P 的长度为 n，理论上来说，最坏情况下迭代 m - n + 1 轮，每轮最多进行 n 次对比，当 m >> n 时，渐进时间复杂度为 O(mn)

KMP

再看一个例子

按照原来的思路，在比较到 i = 7 时，我们需要重新从 s = 1, i = 0 继续比较；但 KMP 算法告诉我们，在重新比较的时候，只需将字符串 P 需要比较的位置重置到 i = 2 即可。

原因是我们发现 P 串有子串 ACT 和 ACY，当 i = 7 发现 T 和 Y 不匹配的时候，我们确认 S 串 j = 5 开始的 AC 不匹配对应 P 串 i = 5 开始的 AC，但可能匹配 P 串 i = 0 开始的 AC。

这就是 KMP 算法的核心思想：使用一个数组 next 来保存 P 串元素不匹配时，下一步重新开始的 P[i] 的位置；其中 next[i] 表示 P 串 [0, i - 1] 的子串里 最长公共前后缀的长度，next[0] 为 -1，表示需要 j 移到 j + 1 开始匹配。

最长公共前后缀：例如对于字符串 abcba：

• 前缀包括：a, ab, abc, abca，不包括本身；
• 后缀包括：bcba, cba, ba, a，不包括本身；
• 最长公共前后缀：a，长度为 1.

所以对于 S 串和 P 串，有以下 next：

匹配过程变成：

1. 比较到 j = i = 7 时，发现 T 和 Y 不一样，对应的 next[7] = 2，意味着只需要将 P[2] 和 S[7] 开始继续比较即可；
2. 继续比较 j = 7, i = 2 直到 j = 9, i = 4 时，发现 K 和 P 不一样，对应的 next[4] = 0，我们重置 i = 0；
3. 继续比较 j = 9, i = 0，发现 K 和 A 不一致，对应的 next[0] = -1，把 j 设成 10；
4. 继续比较 j = 10, i = 0，直到 j = 17, i = 7 匹配结束

算法实现

KMP 主算法

const kmp = (s, p) => {
    const next = buildNext(p)
    let matchPIdx = 0;
    for (let i = 0; i < s.length; i++) {
        if (matchPIdx === p.length) return true
        if (s[i] !== p[matchPIdx]) {
            while (next[matchPIdx] !== -1 && p[matchPIdx] !== s[i]) {
                matchPIdx = next[matchPIdx]
            }
        }
        matchPIdx++
    }
    return matchPIdx === p.length
}

构造 next 表

const buildNext = p => {
    const next = [-1]
    let nextIdx = 0
    let matchPIdx = -1  // nextIdx - 1 的子串里找
    while (nextIdx < p.length - 1) {
        if (matchPIdx === -1 || p[matchPIdx] === p[nextIdx]) {
            const pos = nextIdx + 1 // next 数组要设置的位置
            const curLen = matchPIdx + 1    // 前后缀的长度
            next[pos] = curLen  // 赋值
            // 下个位置
            nextIdx++
            matchPIdx++
        } else {
            /** 
             * next[matchPIdx]
             * 含义是 p[0]~p[matchPIdx - 1] 的最长前后缀长度；
             * matchPIdx = next[matchPIdx]
             * 把匹配指针设置到不匹配的位置 next[matchPIdx] - 1的下一个位置；
             * 
             * 利用了 next 的中间产物，是一种类似 KMP 的思想
             */
            matchPIdx = next[matchPIdx]
        }
    }
    return next
}