KMP算法，next表的创建。

⭐KMP算法

假设我们现在有一段主串 S（目标串）和子串 P（模式串），此时的需求是在主串S中找到一个与子串P相等的子串，如果找到了就返回子串P在主串S中第一次出现的位置。

对于KMP算法来说，主要特点就是主串（目标串）不用回溯，主串指针i一直往后面移动，只有子串（模式串）的指针j在回溯。这就大大减少了模式匹配算法的比较次数以及回溯次数。KMP算法可以在$O(m+n)$的时间复杂度量级上完成串的模式匹配。

KMP可以总结为如下：

• 如果模式串和目标串匹配成功，长串短串都加一
• 如果模式串和目标串没有匹配成功：
• • 目标串不回溯
  • 模式串回溯到匹配未成功的字符前的子串的相同的真前缀和真后缀的最大长度

var strStr = function (haystack, needle) {
    const hlen = haystack.length, nlen = needle.length;
    // i,j 分别指向主串和子串串
    let i = 0, j = 0;
    const next = getNext(needle)
    while (i < hlen && j < nlen) {
        // 如果匹配 都指向下一位  j=-1相当于入口条件
        if (j === -1 || haystack[i] === needle[j]) {
            i++; j++;
            continue;
        }
        // 否则子串按照next表回溯
        else {
            j = next[j]
        }
    }
    // 匹配成功 返回第一个匹配字母索引
    if (j === nlen) {
        return i - j
    }
    // 否则匹配失败
    return -1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

所以关键是获取最大长度：即next表的创建。

next表实际记录的是当前字符p(j)前面的字符串的最大相同前后缀长度。

如以下例子，
字符串

刚开始索引0前面没有字符串next[0]设为-1。
索引1前面字符串为单字符’a’，next[1]设为0。
索引2前面的字符串为’ab’，最大相同前后缀数目为0，所以next[2]=0。
索引3前面的字符串为’aba’，最大相同前后缀数目为1，所以next[3]=1，也就是next[ p(k) ]=1。
$\cdots \cdots$
同理 ，索引j前面字符串’aba…aba’，最大相同前后缀长度为3，next[j] = 3。

索引：0 1 2 3,…,j-3,j-2,j-1,j

next表 ：-1 0 0 1,…,0 1 2 3,…

比如此时已经匹配了’aba’，k=3, next[j]=3。继续对比p[j]与p[k]。

若此时p[j] = p[k]，很明显，最大相同前后缀长度继续+1, next[j++]=k++ = 4。

而当p[j] != p[k]时，才是最关键的，这个时候k该如何回溯。

当不相等时，我们要找的就是j前面的最大相同前后缀’aba’的最大相同前后缀数目。这里就是’aba’的最大前后缀’a’，数目为1，其实就是next[k]的值1。
我们可以不用对比索引0的’a’，而可以直接从索引2的’b’开始对比。

更直观的如下图，其实就是看字符串这两块相同的部分(因为字符串本身是相同的，所以就是看p(k)最大前后缀长度），很明显，有相同的则不用重复比较。k可以回到d这个位置再与p(j)继续进行比较。

然后重复上面操作。

若没有相同字符串，即p(k)=0，

会回到开头位置k=0处，开始新的对比。

var getNext = function (p) {
    const plen = p.length;
    let next = new Array(plen);
    next[0] = -1    // next[0]初始化为-1, 表示子串已经滑动到头  为入口
    let k = -1;     // p[k]表示前缀子串
    let j = 0;      // p[j]表示后缀子串
    while (j < plen - 1) {
        // next表next[j]记录的其实是j位置前（不包含j）的字符串所包含的最大相同前缀后缀
        // 相等则直接记录next[j++] = k+1
        if (k === -1 || p[j] === p[k]) {
            k++;
            j++;
            next[j] = k;
        }
        // 不相等 k回溯 直到相等或者回到起点
        // 重点是k的回溯位置  为当前最大相同前缀后缀的最大相同前缀后缀
        else {
            k = next[k];
        }
    }
    return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22