kmp.js

function getMaxPrefixAndSuffix(P) {
    let i = 0;
    let len = 0;

    for (let i = P.length - 1; i >= 0; --i) {
        if (P.slice(0, i) === P.slice(-i)) {
            return i;
        }
    }

    return 0;
}

function computeX(pattern) {
    let x = [0];

    for (let i = 1; i < pattern.length; ++i) {
        x.push(getMaxPrefixAndSuffix(pattern.slice(0, i + 1)));
    }

    return x;
}

function kmpsearch(str, pattern) {
    const x = computeX(pattern);
    let k = 0;
    let s = 0;

    while (k < pattern.length && s <(str.length - pattern.length)) {
        if (str[s + k] === pattern[k]) {
            k++;

            if (k === pattern.length) {
                return s;
            }
        } else {
            k = x[Math.max(k-1, 0)];
            s = s + Math.max(k, 1);
        }
    }
    return -1;
}