模式串匹配

暴力解法

function findIndex(origin, target) {
    for (let i = 0; i < origin.length; i++) {
        for (let j = 0, k = i; j < target.length && origin[k] === target[j]; k++, j++) {
            if (j + 1 === target.length) {
                return i
            }
        }
    }
    return -1
}

KMP

function kmp(origin, target) {
    let i = 0,
        j = 0,
        oLen = origin.length,
        tLen = target.length;
    const getNext = (s) => {
        let arr = [-1],
            l = -1, r = 0,
            sLen = s.length;
        while (r < sLen - 1) {
            if (l === -1 || s[l] === s[r]) {
                l++;
                r++;
                arr[r] = l
            } else {
                l = arr[l]
            }
        }
        return arr
    }
    let next = getNext(target)
    while (i < oLen && j < tLen) {
        if (j === -1 || origin[i] === target[j]) {
            i++
            j++
        } else {
            j = next[j]
        }
    }
    return j === tLen ? i - j : -1
}