kmp算法

function kmp(S, T) {
    if (!S || !T || T.length < S.length) return 0;
    const next = getNext(S);
    return getCount(next, S, T);
}
function getNext(needle) {
    const next = Array(needle.length).fill(0);
    for (let i = 1, j = 0; i < needle.length; ++i) {
        while (j > 0 && needle[i] !== needle[j]) j = next[j - 1];
        if (needle[i] === needle[j]) j++;
        next[i] = j;
    }
    return next;
}
function getCount(next, needle, haystack) {
    let count = 0;
    for (let i = 0, j = 0; i < haystack.length; i++) {
        while (j > 0 && haystack[i] !== needle[j]) j = next[j - 1];
        if (haystack[i] === needle[j]) ++j;
        if (j === needle.length) {
            count++;
            j = next[j - 1];
        }
    }
    return count;
}