KMP 算法：next 数组与避免回溯
基于通用算法套路 · 核于 2026-07
速查
- KMP 核心：利用模式串自身的结构，失配后主串指针
i绝不回退，只移动模式串指针j——把朴素法最坏O(n·m)压到严格O(n+m)。 - next 数组定义：
next[j]= 模式串前缀p[0..j-1]的「真前缀」与「真后缀」中最长的公共串长度（也写作「最长公共前后缀长度」/ LPS，longest proper prefix which is also suffix）。 - next 数组的意义：失配发生在
p[j]时（即p[0..j-1]已匹配），模式串可以右移到「p[0..next[j]-1]对齐到原p[j-next[j]..j-1]位置」而不丢任何已匹配信息——主串i原地、j = next[j]继续。 - next 构造 = 模式串自匹配：用
i扩右端、len跟踪当前 LPS 长度，p[i] === p[len]则next[i+1] = ++len并i++，否则len = next[len]回退——本质是「模式串跟自己做 KMP」。 - 匹配过程：
i扫主串、j扫模式串；相等则i++, j++；j === m命中（记录i-m，j = next[j]续找）；失配则j = next[j]（若j === 0则i++）。 - 复杂度：预处理
nextO(m) + 匹配 O(n) = O(n+m)；空间 O(m)。 - 为何 next = 最长公共前后缀：只有前缀 = 后缀时，把前缀挪到后缀位置才不丢已匹配字符；取「最长」是为了不漏掉可能的匹配（更短的后移会被「最长」覆盖到的位置包含）。
- 两种 next 约定：①「失配跳到
next[j]」（next[0]=0，本文约定）；②「优化版 next」（失配若p[next[j]] === p[j]再跳一次）。考试题注意题干约定，本叶用约定①。 - 易错：
next索引含义（next[j]对应前缀p[0..j-1]，下标差 1）；真前缀/真后缀（不能是整个串，所以next[0]=0）；j回退到 0 时要i++别死循环。
一、KMP 核心：主串不回溯
朴素法的浪费在于「失配后丢掉已匹配的 j 个字符信息」。KMP 的洞察是：既然 p[0..j-1] 已经和主串某段相等，而 p 自身又有「前缀 = 后缀」的结构，那么失配后只需把模式串的某个前缀重新对齐到已匹配段的某个后缀位置，就能复用一部分已匹配字符——主串指针 i 完全不用动。
具体地，当 p[j] 与 s[i] 失配时（说明 p[0..j-1] === s[i-j..i-1] 已成立），设 p[0..j-1] 的最长公共前后缀长度为 len = next[j]。那么 p[0..len-1] === p[j-len..j-1]。又因为 p[j-len..j-1] === s[i-len..i-1]（已匹配），所以 p[0..len-1] === s[i-len..i-1]——把模式串右移 j - len 位后，p[0..len-1] 自动对齐了，直接从 p[len] 与 s[i] 继续比较即可。这就是 j = next[j] 的来源，主串 i 一步都没退。
二、next 数组：最长公共前后缀
next[j] 定义为模式串前缀 p[0..j-1] 的「真前缀」与「真后缀」中最长的公共串长度。「真」表示不能取整个 p[0..j-1] 本身（否则永远等于自身，无意义）。
以 p = "abcabd" 为例：
j | p[0..j-1] | 真前缀集合 | 真后缀集合 | 最长公共前后缀 | next[j] |
|---|---|---|---|---|---|
| 0 | ``（空前缀） | — | — | — | 0 |
| 1 | a | ∅ | ∅ | 无 | 0 |
| 2 | ab | a | b | 无 | 0 |
| 3 | abc | a,ab | c,bc | 无 | 0 |
| 4 | abca | a,ab,abc | a,ca,bca | a | 1 |
| 5 | abcab | a,ab,abc,abca | b,ab,cab,bcab | ab | 2 |
| 6 | abcabd | a,ab,abc,abca,abcab | d,bd,abd,cabd,bcabd | 无 | 0 |
直观规律：next[j] 沿着 p 的前缀「延伸」——p[0..j-1] 在 p[j] 处能续上之前的最长公共前后缀就 +1，续不上就回退。
三、next 数组构造：模式串自匹配
next 的构造本身就是「模式串跟自己做一次 KMP 匹配」。用 i 从 1 开始扩展右端字符，len 记录当前已知的「p[0..i-1] 的最长公共前后缀长度」（即 next[i] 的候选）：
// 构造 next 数组：next[j] = p[0..j-1] 的最长公共前后缀长度
function buildNext(p) {
const m = p.length;
const next = new Array(m + 1).fill(0); // 长度 m+1，next[0..m]
let i = 1, len = 0; // i 扩右端，len = 当前 LPS 长度
while (i < m) {
if (p[i] === p[len]) { // 能续上：LPS +1
len++;
next[i + 1] = len; // 注意 next[i+1] 对应前缀 p[0..i]
i++;
} else if (len > 0) {
len = next[len]; // 续不上：回退到更短的 LPS（不推进 i）
} else {
next[i + 1] = 0; // len 已为 0 还不等：直接置 0
i++;
}
}
return next;
}p[i] === p[len]：当前字符能延续之前的 LPS，长度+1，next[i+1] = len，i右移。- 不等且
len > 0：不能延续，但别放弃——回退到len = next[len]（之前 LPS 的 LPS），再试一次能否续上。i不动，下一轮循环用新的len重比。 - 不等且
len === 0：已经回退到无可回退，next[i+1] = 0，i右移。
这个「回退到 next[len]」的递归跳转与匹配阶段的失配跳转完全同构——所以叫「自匹配」。
四、匹配过程：O(n+m)
有了 next 数组，匹配就是让 i 单调扫过主串、j 在模式串里前进或回跳：
// KMP 匹配：返回 p 在 s 中所有出现起点下标
function kmpSearch(s, p) {
const n = s.length, m = p.length;
const next = buildNext(p);
const res = [];
let i = 0, j = 0; // i 扫主串，j 扫模式串
while (i < n) {
if (s[i] === p[j]) { // 当前字符相等：双双向右
i++; j++;
if (j === m) { // 完整匹配
res.push(i - m); // 记录起点
j = next[j]; // 续找下一个（复用 LPS，i 不退）
}
} else if (j > 0) {
j = next[j]; // 失配：模式串右移（主串 i 不动）
} else {
i++; // j 已为 0 还失配：主串前进
}
}
return res;
}主串指针 i 始终单调递增，从不回退——这是 KMP 严格线性的根本原因。模式串指针 j 虽会回跳，但每次回跳都是 next[j] < j（向左），而 j 增加的总次数受 i 增加（≤ n）约束，分摊后 j 的总回跳次数也是 O(n)，故匹配阶段整体 O(n)。
五、为何 next = 最长公共前后缀
两个要求——「前后缀」与「最长」——各有道理：
- 为什么是「前后缀」：失配后要把模式串的前缀重新对齐到已匹配段的后缀位置，前提是这个前缀本身等于那个后缀（否则对齐也对不上）。所以候选右移量对应的长度必须是「既是前缀又是后缀」的长度。
- 为什么是「最长」：设 LPS 长度为
len，则所有更短的「公共前后缀长度」len' < len对应的更小右移位置，都已经包含在「先跳len、再失配还能继续next[len]往更短跳」的链路里。如果一开始就跳到最短，会漏掉「跳到最长刚好能匹配」的那些位置。取「最长」保证不漏，靠失配链路保证不冗余。
一句话：最长 = 保证不漏可能匹配的右移位置；前后缀 = 保证对齐后已匹配字符不丢。
交互演示
- KMP 可视化演示 —— next 数组构造与「主串不回溯」的匹配过程
下一步
KMP 解决了「精确单模式、严格线性」的问题。但在多模式同时匹配或工程实测最快的场景，有更合适的选择——Rabin-Karp 的滚动哈希与 Boyer-Moore 的坏字符/好后缀跳跃，见 Rabin-Karp 与 Boyer-Moore。