题解 | #kmp算法#
kmp算法
https://www.nowcoder.com/practice/bb1615c381cc4237919d1aa448083bcc
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算模板串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,
};
