/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 计算模板串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
};