题解 | #kmp算法#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
function kmp( S ,  T ) {
    let res = 0; 
    let next = new Array(S.length).fill(0);
    getNextIndex(S, next);
    let j=0;
    for(let i = 0;i < T.length;i++)
        {
            while(j > 0 && T[i] != S[j])
                j = next[j - 1];
            if(T[i] == S[j])
                j++;
            if(j == S.length)
            {
                res++;
                j = next[j - 1];
            }
        }
    return res;
    
}

function getNextIndex(S, next) {
    let j = 0;
    let i = 1;
    for(let i = 1; i< S.length; i++) {
        while(j > 0 && S[i] != S[j])
            j = next[j - 1];
        if( S[i] == S[j] ) {
            j++;
        }
        next[i] = j;
    }
}


module.exports = {
    kmp : kmp
};