KMP 算法解析(JavaScript)

[dengwanc]

KMP 算法作为入门级别稍带难度的算法，拥有如下属性，可以看作动态规划的一种应用，可以看作自动机的一种应用。

背景

求解主串(text)中是否有模式串(pattern)，比如 cab 在 abcabe 中。
text 的长度记为 M，pattern 的长度记为 N。

思想

暴力法，会简单的把 pattern 串往前移动一位进行匹配，此时的复杂度是O(M*N)。
能不能想办法把复杂度降一个阶，不是把 pattern 串往前移动一位，而是移动尽可能多的位。

0 1 2 3 4 5 6 7 8 9 // 索引
    i
a b c a b e a b d a
a b e a b r
    j

next 数组

如上图：
对于模式串，当匹配到 j == 4 时，此时这一位能够代表整个 pattern 的哪个位置呢？实际上它可以代表 1
对于模式串，当匹配到 j == 5 时，此时这一位能够代表整个 pattern 的哪个位置呢？实际上它可以代表 2
那么 j == 4 时恰好不匹配了，可以把 j 移动到它代表的位置 1
那么 j == 5 时恰好不匹配了，可以把 j 移动到它代表的位置 2

这些代表位就是 next 数组。

匹配过程

如上图：
abeabr 的 next 数组是 [0, 0, 0, 0, 1, 2]，
当 i == 2 且 j == 2 时，text[i] !== pattern [j], 此时程序查 next[2] 发现是 0 那就是说，从头匹配吧。
当 i == 8 且 j == 5 时，text[i] !== pattern [j], 此时程序查 next[2] 发现是 2 那就是说，从 j = 2 开始匹配吧，因为 pattern 在位置 2 之前字符和主串 i 之前的 字符都相等。

经验

• 一味的看博客不如自己动手写写画画
• 就算看懂了，也一定要自己亲自动手写一遍代码
• 粗心大意是成为编程高手的最大障碍

以下是代码实现

求出 next 数组需要 O(N) 时间 + O(N) 空间，匹配过程需要 O(M)，综上：
时间复杂度 O(M + N)
空间复杂度 O(N)

// @ts-check

/**
 * KMP Algorithm
 * @param {string} text
 * @param {string} pattern
 * @return {number}
 */
function KMPStringMatch(text, pattern) {
    const next = getNext(pattern);
    const tlength = text.length;
    const plength = pattern.length;
    const FIRST_OF_PATTERN = 0;

    let i = 0;
    let j = 0;
    while (tlength > i) {
        if (text[i] === pattern[j]) {
            if (j === plength - 1) {
                return i - j;
            }
            i++;
            j++;
        } else {
            if (j === FIRST_OF_PATTERN) {
                i++;
            }
            j = next[j];
        }
    }

    return -1;
}

/**
 * 
 * @param {string} pattern
 * @return {number[]}
 */
function getNext(pattern) {
    let ret = [0];
    let length = pattern.length;
    let i = 0;
    let j = 1;

    for (;j < length; j++) {
        if (pattern[i] === pattern[j]) {
            ret[j] = i;
            i++;
        } else {
            ret[j] = i;
            i = 0;
        }
    }

    return ret;
}

/** test cases */
let r1 = KMPStringMatch('abeabfabcabe', 'abcabe');
let r2 = KMPStringMatch('abeabfabcabe', 'cc');
let r3 = KMPStringMatch('abeabfabcabe', 'ea');
let r4 = KMPStringMatch('abeabfabcabe', 'caf');
let r5 = KMPStringMatch('abeabfabcabe', 'gp');
let r6 = KMPStringMatch('abeabfabcabe', 'abeabfabcabe');

console.assert(r1 === 6);
console.assert(r2 === -1);
console.assert(r3 === 2);
console.assert(r4 === -1);
console.assert(r5 === -1);
console.assert(r6 === 0);

^{如果您觉得此文有帮助，可以描二维码打赏点钱给我}