题解 | #kmp算法#

/**

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

 *

 * 计算模板串S在文本串T中出现了多少次

 * @param S string字符串 模板串

 * @param T string字符串 文本串

 * @return int整型

 */

function kmp(S, T) {

    let res = 0;

    let next = nextFun(S);

    let i = 0;

    let j = 0;

    while (i < T.length) {

        if (T[i] == S[j]) {

            i++;

            j++;

        } else if (j > 0) {

            j = next[j - 1];

        } else {

            i++;

        }

        if (j == S.length) {

            res++;

            j = next[j - 1];

        }

    }

    return res;

}

function nextFun(S) {

    let next = [0];

    let prefixLen = 0;

    let i = 1;

    while (i < S.length) {

        if (S[prefixLen] == S[i]) {

            prefixLen++;

            i++;

            next.push(prefixLen);

        } else {

            if (prefixLen == 0) {

                next.push(0);

                i++;

            } else {

                prefixLen = next[prefixLen - 1];

            }

        }

    }

    return next;

}

module.exports = {

    kmp: kmp,

};