KMP字符串匹配算法

应用: 字符串匹配，在字符串（也叫主串）中的模式（pattern）定位问题
时间复杂度: O(m+n)
算法核心: 时间换空间。利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速
匹配的目的。
帮助模式串顺利的跳过不必要的比较，直接后移到一部分前缀已经匹配的位置，开始下一次的比较。
更准确的将是移动到：最长公共真前后缀匹配的位置。

基本思路：

当我们发现某一字符不匹配时，由于已经知道之前遍历过的字符，利用这些信息来避免暴力算法中“回退(backup)”的操作。也就是主串的指针 i 不会回退，而且一直向前移动。只需要遍历一次主串就可以完成匹配。

动画流程：

图2中，主串和子串的AB相同，我们完全可以跳过它们，避免重复的比对。接下来只需要继续测试后面的字符就好了。

🤔 此时你就会问，我们怎么知道应该跳过多少个字符呢？
这里就需要用到 KMP 中定义的 next 数组了。

:::info next数组代表在匹配失败的时候，子串中可以 “跳过匹配” 的字符个数。 :::

如上图，当遇到字符不匹配时，为2的情况，就代表我们可以跳过前两个字符的比较，将子串指针 j 指向下标2处

伪代码：

const kmp_search = function (string, patt) {
    let next = build_next(patt); // 假设我们已经算出了 next 数组
    let i = 0; // 主串中的指针
    let j = 0; // 子串中的指针
    while (i < string.length) {
        if (string[i] === patt[j]) { // 字符匹配，指针后移
            i++
            j++
        } else if (j > 0) { // 字符串失配，j 指针回退，根据 next 跳过子串前面的部分字符的比较
            j = next[j - 1];
        } else { // 子串第一个字符就失配（不匹配且 j 指针为0）
            i++;
        }
        if (j === patt.length) { // 如果指针 j 已经到达了子串的末尾，则表示匹配成功，返回匹配的起始位置即可。
            return i - j;
        }
    }
}
// 时间复杂度：O(n)，n 代表主串 string 的长度。

这段程序逻辑还是比较简单的，我们注意到指针 i 永远是不递减的，这也是 KMP 算法的精髓和快的原因。

动画流程 / 带next：

next数组的生成

之前我们讲到过，next 数组代表在匹配失败的时候，子串中可以 “跳过匹配” 的字符个数。

凭什么可以这么做？

因为我们之前成功匹配的最后两个AB和跳过的最前面两个AB是完全一样的。
换句话说，对于子串的前4个字符，它们拥有一个共同的前缀和后缀AB。所以 next 数组的本质其实就是 寻找子串中“相同前后缀的长度”，并且一定是最长的公共真前后缀。
如下图中的A A 虽然相同，当他并不是最长的，最长的应为ABA，长度为3，next为3。

buildNext代码

const build_next = function (patt) {
    const next = [0]; // next 数组（初值元素一个0）
    prefix_len = 0; // 当前共同前后缀的长度
    let i = 1;
    while (i < patt.length) {
        if (patt[prefix_len] === patt[i]) { // 如果下个字符依然相同，则可以构成一个更长的前后缀
            prefix_len++;
            next.push(prefix_len);
            i++;
        } else {
            if (prefix_len === 0) {
                next.push(0);
                i++;
            } else {
                // 查表看看是否存在更短的前后缀
                prefix_len = next[prefix_len - 1];
            }
        }
    }
    return next;
}

应用

题目：LC.实现strStr()

var strStr = function (haystack, needle) {
    const next = build_next(needle); // 计算 next 数组

    let i = 0; // 主串中的指针
    let j = 0; // 子串中的子针
    while (i < haystack.length) {
        if (haystack[i] === needle[j]) {
            i++;
            j++;
        } else if (j > 0) {
            j = next[j - 1]; // 字符串失配，j 指针回退，根据 next 跳过子串前面的部分字符的比较
        } else {
            i++;
        }

        // 如果指针 j 已经到达了子串的末尾，则表示匹配成功，返回匹配的起始位置即可。
        if (j === needle.length) return i - j;
    }
    return -1;
};

const build_next = function (needle) {
    const next = [0];
    let prefix_len = 0;
    let i = 1;
    while (i < needle.length) {
        if (needle[prefix_len] === needle[i]) {
            prefix_len++;
            next[i] = prefix_len;
            i++
        } else if (prefix_len === 0) {
            next.push(0);
            i++;
        } else {
            prefix_len = next[prefix_len - 1];
        }
    }
    return next;
}

var strStr = function(haystack, needle) {
    if(needle == "")return 0;
    let next = getNext(needle);
    let hi = 0;
    let ne = 0;
    while(hi<haystack.length){
        if(ne == -1 || haystack[hi] == needle[ne]){ //相等情况
            if(ne == needle.length - 1)return (hi - needle.length + 1);
            hi++;
            ne++;
        }else{ //失配情况
            ne = next[ne];
        }
    }
    return -1;
};

function getNext(needle){ //获取next数组
    let next = [];
    next[0] = -1;
    let i = 0;
    let j = -1;
    while(i < needle.length){
        if(j == -1 || needle[i] == needle[j]){
            next[++i] = ++j;
        }else{
            j = next[j] //回溯
        }
    }
    return next;
}