AcWing 831. KMP字符串 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-20 18:06:43
,
所有人可见
,
阅读 820
let kmp = (src, pattern) => {
//字符串从1开始匹配
let s = '*' + src, p = '*' + pattern;
let sLen = src.length, pLen = pattern.length;
let next = new Array(pLen).fill(0);
let result = [];
//数组next i为p的位置,j为成功匹配的长度
for (let i = 2, j = 0; i <= pLen; i++) {
while (j > 0 && p[i] !== p[j + 1]) j = next[j];
if (p[i] === p[j + 1]) j++;
next[i] = j;
}
for (let i = 1, j = 0; i <= sLen; i++) {
while (j > 0 && s[i] !== p[j + 1]) j = next[j];
if (s[i] === p[j + 1]) j++;
if (j === pLen) {
result.push(i - pLen);
//回退后重新开始
j = next[j];
}
}
return result;
}
let buf = '';
process.stdin.on('readable', () => {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputArgs = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
process.stdin.on('end', () => {
let src = '', pattern = '';
buf.split('\n').forEach((line, lineIdx) => {
if (lineIdx === 1) {
pattern = line;
} else if (lineIdx === 3) {
src = line;
console.log(kmp(src, pattern).join(' '));
}
});
});