DT走过的路

给出两个字符串 S（主串）、T模式串），输出 T 在 S中第一次出现的起始下标

若不存在返回 -1。等价于实现 indexOf，要求用 KMP。

示例

输入：

S = "ababcabcacbab", T = "abcac"

输出：

5

const sInput = "ababcabcacbab";
const tInput = "abcac"

function findSubstring(s, t) { 
    const index = s.indexOf(t);
    console.log(index);
}

findSubstring(sInput, tInput);

‌采用暴力比对方式，需要利用双层for循环实现

function findSubstring2(s, t){
    let index = -1;
    for(let i = 0; i < s.length - t.length + 1; i++){ 
        for(let j = 0; j < t.length; j++){
            if(s[i+j] !== t[j]){
                break;
            }
            if(j === t.length - 1){
                index = i;
            }
        }
    }
    console.log(index);
}

KMP算法是一种高效的字符串匹配算法‌，核心是利用已匹配信息减少重复比较，让主串指针不回溯，时间复杂度从暴力匹配的$O(nm)$O(nm)降到$O(n+m)$。‌‌

这算法到底在干啥

就是给定两个字符串，判断子串是否在主串中出现，并返回出现位置。暴力匹配每次不匹配就让主串指针回退重新开始，KMP则让主串指针一直向前走，只让子串指针根据已匹配信息回退到合适位置。‌‌

需要了解 前缀、后缀、最长相等前后缀。

前缀：不包含最后一位的所有子串

后缀：不包含第一位的所有子串

最长相等前后缀长度（LPS）：最长同时相等的前缀、后缀长度，记为 next[i]

next数组处理逻辑

1. 初始化 j=0,next = new Array(m).fill(0)
2. 前后缀不相同的情况，使用while，而不是if，while(j>0 && s[i]!=s[j]) j=next[j-1]
3. 前后缀相同的情况，j++
4. 更新next数组 next[i] = j

function getNext(pattern) {
    const m = pattern.length;
    const next = new Array(m).fill(0);
    let j = 0;
    for (let i = 1; i < m; i++) {
        while (j > 0 && pattern[i] !== pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] === pattern[j]) {
            j++;
            next[i] = j;
        }
    }
    return next;
}

a a b a a f
j
 i
0 1 0 1 2 0
next[i]的值是j的当前位置++

如果输入：aabaaf
[ 0, 1, 0, 1, 2, 0 ] next

KMP 匹配主逻辑

• i：主串 S 指针；j：模式串 T 指针
• S[i] == T[j]：i++, j++
• j 走到模式串末尾：匹配成功，返回起始下标 i - j
• 失配且 j≠0：j = next[j-1]
• 失配 j=0：i++

function KMP(s, t) {
    const n = s.length, m = t.length;
    if (m === 0) return 0;
    const next = getNext(t);
    let i = 0, j = 0;
    while (i < n) {
        if (s[i] === t[j]) {
            i++, j++;
        }
        if (j === m) return i - j;
        if (i < n && s[i] !== t[j]) {
            if (j !== 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

console.log(KMP(sInput, tInput));