KMP 字符串匹配的思路是什么？
暴力匹配在失配时把模式串只往后挪一位、从头再比，最坏 O(n × m)。KMP 先为模式串算出 next 数组：next[i] 是前 i + 1 个字符里，既是前缀又是后缀的最长长度。失配时主串指针不回退，模式串直接跳到 next 指出的位置继续比，整体 O(n + m)。JS 里日常查找直接用 indexOf 或 includes，KMP 主要考查对前缀函数的理解。
简答
在
aaaaaaab里找aaab：暴力做法从每个位置开始逐个比，比到第 4 个字符失配，就把起点往后挪一位、模式串从头再比。可前面已经比过的aaa明明知道是什么，却全部重比。主串长 n、模式串长 m 时，最坏要比 O(n × m) 次。KMP 的想法是：失配时，已经匹配上的那一段就是模式串的一个前缀，内容完全已知。如果这段的结尾和模式串的开头有重叠，就可以把模式串直接挪过去，让重叠部分对齐，从重叠之后接着比，主串指针一步也不用回退。
重叠多长，只和模式串有关，所以预先算好一个
next数组：next[i]表示模式串前 i + 1 个字符组成的子串里，最长的“相等的真前缀和真后缀”有多长。比如abab的真前缀ab和真后缀ab相等，next[3]就是 2。算next用 O(m)，匹配用 O(n)，总共 O(n + m)。要注意，
next的定义有好几种写法，有的整体右移一位、首项写 -1，看别人的代码时先确认含义。实际开发里查找子串直接用indexOf或includes，引擎有自己优化过的实现；KMP 的价值在于面试考查对前缀函数的理解，以及它在流式匹配这类主串不能回退的场景里的用法。
先算 next 数组
buildNext 里的 length 是“当前已知的最长相等前后缀长度”。看失配时它怎样往回退：不是退到 0，而是退到 next[length - 1]，也就是在更短的前缀里继续找重叠。
function buildNext(pattern) {
const next = new Array(pattern.length).fill(0);
let length = 0;
for (let i = 1; i < pattern.length; i++) {
while (length > 0 && pattern[i] !== pattern[length]) {
length = next[length - 1];
}
if (pattern[i] === pattern[length]) length++;
next[i] = length;
}
return next;
}
console.log(JSON.stringify(buildNext('abab'))); // [0,0,1,2]
console.log(JSON.stringify(buildNext('aabaaab'))); // [0,1,0,1,2,2,3]
console.log(JSON.stringify(buildNext('aaaa'))); // [0,1,2,3]
console.log(JSON.stringify(buildNext('abc'))); // [0,0,0]
console.log(JSON.stringify(buildNext(''))); // []
aabaaab 的 next[5] 为什么是 2？前 6 个字符是 aabaaa。到 i = 4 时，aabaa 的最长相等前后缀是 aa，length 是 2；i = 5 的字符 a 要和 pattern[2] 也就是 b 比，不相等，于是 length 退到 next[1] 即 1，再拿 a 和 pattern[1] 的 a 比，相等，length 变成 2。对应的前后缀是 aa。
为什么退到 next[length - 1] 就够了，不会漏掉更长的？当前长度为 length 的前缀和后缀相等，所以“后缀的后缀”就等于“前缀的后缀”。比 length 短、还能对上的候选，只能是这个前缀自己的相等前后缀，最长的一个正是 next[length - 1]。
为什么 i 从 1 开始？真前缀和真后缀不能是整个串本身，单个字符没有真前后缀，所以 next[0] 总是 0。
用 next 做匹配
匹配和建表几乎是同一段代码，只是拿主串的字符和模式串比。j 是模式串已经匹配上的长度，等于 m 时就找到一处。
function buildNext(pattern) {
const next = new Array(pattern.length).fill(0);
let length = 0;
for (let i = 1; i < pattern.length; i++) {
while (length > 0 && pattern[i] !== pattern[length]) length = next[length - 1];
if (pattern[i] === pattern[length]) length++;
next[i] = length;
}
return next;
}
function kmpSearchAll(text, pattern) {
if (pattern.length === 0) return [0]; // 与 indexOf 的约定一致：空串出现在开头
const next = buildNext(pattern);
const result = [];
let j = 0;
for (let i = 0; i < text.length; i++) {
while (j > 0 && text[i] !== pattern[j]) j = next[j - 1]; // 主串指针 i 不回退
if (text[i] === pattern[j]) j++;
if (j === pattern.length) {
result.push(i - j + 1);
j = next[j - 1]; // 继续找下一处，允许重叠
}
}
return result;
}
console.log(JSON.stringify(kmpSearchAll('aaaaaaab', 'aaab'))); // [4]
console.log(JSON.stringify(kmpSearchAll('abababab', 'abab'))); // [0,2,4]
console.log(JSON.stringify(kmpSearchAll('hello', 'xyz'))); // []
console.log(JSON.stringify(kmpSearchAll('', 'a'))); // []
console.log(JSON.stringify(kmpSearchAll('abc', ''))); // [0]
console.log('aaaaaaab'.indexOf('aaab'), 'abc'.indexOf('')); // 4 0
为什么说 O(n + m)？i 只往前走，共 n 步。j 每步最多加 1，while 里每次回退都让 j 至少减 1，而 j 不会小于 0，所以整个匹配过程中回退的总次数不超过 j 增加的总次数，也就是不超过 n。建表同理是 O(m)。
abababab 里为什么能找到重叠的三处？找到第一处以后，j 不是清零，而是退到 next[3] 即 2，相当于承认结尾的 ab 可以当作下一次匹配的开头，所以下标 2 和 4 也能找到。只要不重叠的结果时，把这里改成 j = 0 即可。
空模式串返回 [0] 是按 indexOf 的约定：MDN 说明，查找空字符串时，indexOf 返回的是起始位置，没有指定起始位置时就是 0。
常见追问
JS 的 indexOf 用的是 KMP 吗？
规范只规定了
indexOf的结果，没有规定用什么算法，各引擎可以自己选。实际开发直接用indexOf、includes或正则就行，不需要自己写 KMP。
next 数组还能用来做什么？
判断一个字符串能否由某个子串重复多次构成：设长度为 n，
p = n - next[n - 1]，如果next[n - 1] > 0且 n 能被 p 整除，它就由长度为 p 的前缀重复而成。比如abcabc的next最后一项是 3，p 是 3，6 能被 3 整除，答案是abc重复两次。