题解 | kmp算法

使用kmp算法，在每次匹配时count++，记录个数

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

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

    return count

}
module.exports = {
    kmp : kmp
};