Next数组记录模式串各位置最长相等前后缀长度，用于KMP失配时跳转；构建时用双指针模拟自匹配，j回退依赖next[j-1]，需用while而非if确保完全回退。
理解 Next 数组的作用
next 数组是 kmp 算法的核心预处理结构，它记录模式串中每个位置前缀与后缀的最长相等长度。比如模式串 "ababaca"，其 next 数组为 [0,0,0,1,2,3,0]（按 0 起始索引），表示在第 i 位失配时，应跳转到 next[i] 对应的位置继续匹配，避免暴力回退。
Next 数组构建的关键逻辑
构建过程本质是“用模式串自己匹配自己”：对每个位置 i，找 s[0..i-1] 的最长真前缀，同时也是真后缀。用两个指针：j 表示当前已知最长前后缀长度（也即上一位置的匹配状态），i 遍历模式串下标（从 1 开始）。
核心规则：
- 若 s[i] == s[j]，说明可延续之前的匹配，令 Next[i] = j + 1，然后 i 和 j 同时右移
- 若不等，且 j > 0，则回退 j 到 Next[j-1]，尝试更短的前缀
- 若 j == 0 仍不匹配，则 Next[i] = 0，i 继续右移
Java 中数组实现的完整代码
以下是一个清晰、无依赖的静态方法，输入字符串返回 int[] 类型的 Next 数组（0 起始，Next[0] 恒为 0）：
public static int[] buildNext(String pattern) {
if (pattern == null || pattern.length() == 0) return new int[0];
int n = pattern.length();
int[] next = new int[n];
next[0] = 0; // 第一个字符无真前缀
int j = 0; // 当前匹配的前缀长度（也是上一位置的最长前后缀值）
<pre class="brush:java;toolbar:false;">for (int i = 1; i 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1]; // 回退到上一个可能的匹配长度
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
例如调用 buildNext("ababaca") 返回 [0,0,0,1,2,3,0]；调用 buildNext("aaaa") 返回 [0,1,2,3]。
常见易错点提醒
初学者常在边界和回退逻辑上出错：
- 不要把 Next[0] 设为 -1 —— 本实现采用“长度定义”，Next[i] 表示 s[0..i] 的最长公共前后缀长度，非“跳转下标”。若需 KMP 主匹配中使用 -1 偏移风格，可在构建时统一减 1，但语义需自洽
- while 循环不能写成 if —— 单次不匹配可能需多次回退（如 "aaaab" 中末尾 'b' 失配，j 需从 4→3→2→1→0）
- next[j-1] 是安全的 —— 因 while 条件保证了 j > 0，所以 j-1 ≥ 0
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
