next数组不能用j=next[j-1]单次跳转，因为需循环回退直到字符匹配或j=0；next[i]表示s[0..i]最长真前后缀长度，主流实现next[0]=0；KMP搜索中j仅在j==0且失配时才推进i，否则按next回退。
为什么 next 数组不能直接用 j = next[j-1] 跳转？
因为 next[j-1] 表示的是前缀 s[0..j-2] 的最长真前后缀长度，它不保证 s[next[j-1]] == s[j-1]。跳过去之后可能字符不匹配，必须在循环中持续回退直到匹配或退到 -1。
常见错误是写成单次赋值：if (s[i] != s[j]) j = next[j-1]; —— 这会漏掉多层不匹配的情况，导致 next 构建错误。
- 正确做法是用
while循环回退：while (j > 0 && s[i] != s[j]) j = next[j-1]; -
j == 0时不能再查next[-1]，所以循环条件必须含j > 0 - 当
s[i] == s[j]，才执行next[i] = j + 1；否则next[i] = 0（隐含在初始化中）
next 数组下标从 0 开始还是从 1 开始？
取决于你如何定义 next[i]：它代表子串 s[0..i] 的最长相等真前后缀长度。主流实现（包括 CLRS 和多数竞赛代码）让 next[0] = 0，即单字符无真前后缀。
注意：有些资料把 next 定义为「匹配失败时应跳转的位置」，此时会设 next[0] = -1，并在主匹配中用 j = next[j]。但构建逻辑本质相同，只是偏移了一位。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 推荐统一用
next[i]表示s[0..i]的最长真前后缀长度，next[0] = 0 - 这样构建和匹配时索引直观，不易混淆边界
- 若看到
next首项为 -1 的代码，说明它把next当作“跳转下标”而非“长度”，两者仅差一个 offset
KMP 主搜索循环里，j 什么时候重置为 0？
不是每次失配都重置为 0。KMP 的核心就是避免暴力回退 —— j 应该跳到 next[j-1] 对应的位置继续比，而不是归零。
只有当 j == 0 且 s[i] != pat[j] 时，才意味着模式串第一个字符就不匹配，这时才让 i++ 继续推进文本串。
- 错误写法：
if (s[i] != pat[j]) { j = 0; i++; }→ 退化成 O(nm) 暴力 - 正确流程：
while (j > 0 && s[i] != pat[j]) j = next[j-1];，然后判断是否匹配 - 匹配成功后
j++；若j == pat.length()，说明找到，接着用j = next[j-1]继续找下一个
完整可运行的 C++ 实现（含注释关键点）
#include <vector>
#include <string>
#include <iostream>
<p>std::vector<int> build_next(const std::string& pat) {
int n = pat.size();
std::vector<int> next(n, 0); // next[0] = 0
int j = 0; // 当前最长前后缀长度，也是上一位置的 next 值
for (int i = 1; i < n; ++i) {
while (j > 0 && pat[i] != pat[j])
j = next[j-1]; // 必须 while，不是 if
if (pat[i] == pat[j])
++j;
next[i] = j; // 注意：这里存的是长度，不是下标
}
return next;
}</p><p>std::vector<int> kmp_search(const std::string& txt, const std::string& pat) {
if (pat.empty()) return {0};
std::vector<int> next = build_next(pat);
std::vector<int> res;
int j = 0;
for (int i = 0; i < txt.size(); ++i) {
while (j > 0 && txt[i] != pat[j])
j = next[j-1];
if (txt[i] == pat[j])
++j;
if (j == pat.size()) {
res.push_back(i - j + 1);
j = next[j-1]; // 找到后立即跳，支持重叠匹配
}
}
return res;
}</p>最易被忽略的一点：build_next 中的 j 初始为 0，对应 next[0] = 0，后续所有 next[i] 都依赖这个起点。一旦这里初始化错（比如设成 -1），整个数组就偏移失效。调试时建议打印前几项 next 值，对照手算验证。
