next数组的本质是模式串每个位置的最长相等真前后缀长度，即对每个i，next[i]表示子串pattern[0..i]中真前缀与真后缀完全相等的最大长度；真前后缀要求长度严格小于子串本身，且该值是KMP算法跳过无效比较的核心依据。
next数组的本质是什么
next数组不是凭空构造的，它记录的是模式串每个位置的「最长相等真前后缀长度」。比如模式串 "ababaca" 在索引 4（字符 'a'）处的 next[4] 是 2，因为子串 "ababa" 的最长真前缀 "ab" 和最长真后缀 "ab" 相等，且长度为 2。
关键点在于：「真前后缀」不能等于整个子串本身，所以长度必须严格小于当前子串长度；而「最长相等」决定了我们每次只关心最大可能匹配长度，这是 KMP 跳过无效比较的核心依据。
手动推导 next 数组的三步法
以模式串 "ababaca" 为例（下标从 0 开始），按位置逐个算 next[i]：
-
next[0] = 0：单字符无真前后缀，固定为 0 - 对每个
i > 0，先设j = next[i-1]，然后尝试扩展：
若pattern[j] == pattern[i]，则next[i] = j + 1；
否则回退到j = next[j-1]（如果j > 0），继续比较，直到j == 0或匹配成功；
若最终不匹配，则next[i] = 0 - 注意边界：当
j == 0且pattern[0] != pattern[i]时，next[i]就是 0
例如算 next[5]（对应字符 'c'）：前一位 next[4] = 2，即 j = 2，比较 pattern[2] == 'a' 与 pattern[5] == 'c' → 不等；回退 j = next[1] = 0，再比 pattern[0] == 'a' 与 'c' → 还是不等 → 所以 next[5] = 0。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
代码实现中容易错的三个细节
用 C++ 写标准 next 数组生成时，常见坑不在逻辑，而在索引和初始值：
- 数组长度必须是
pattern.size()，且next[0]必须显式赋为 0 —— 即使用 vector 初始化为 0，也要确认没被覆盖 - 主循环里
j的更新必须用while (j > 0 && pattern[i] != pattern[j]) j = next[j-1];，漏掉j > 0判断会导致next[-1]访问越界 - 匹配成功后的赋值是
next[i] = j + 1，不是j；失败后next[i]就是 0（无需额外 else）
典型片段：
vector<int> computeNext(const string& pattern) {
int n = pattern.size();
vector<int> next(n, 0);
for (int i = 1, j = 0; i < n; ++i) {
while (j > 0 && pattern[i] != pattern[j])
j = next[j-1];
if (pattern[i] == pattern[j])
++j;
next[i] = j;
}
return next;
}
为什么有的教材用 next[0] = -1？
这是另一种定义方式：把 next[i] 解释为「匹配失败时应跳转到的上一个位置」，而非「最长相等真前后缀长度」。此时 next[0] = -1 表示无路可退，后续所有值整体偏移 -1。两种定义都能工作，但混用会出错。
实际工程中推荐统一用「长度版」（即 next[0] = 0），因为：
• 语义直观，和字符串长度单位一致
• 与 std::string::find 等接口行为更贴近
• 避免在 while 循环里频繁做 +1/-1 调整，降低出错概率
如果你看到别人代码里 next 值普遍比你小 1，先检查是不是定义流派不同——这比调试逻辑错误还容易卡住。
