KMP算法的核心在于理解next数组的物理意义：next[i]表示模式串p[0..i]的最长相等真前缀与真后缀的长度，构建时通过回退到next[j-1]实现高效跳转，匹配时主串指针i绝不回溯。
KMP 算法在 Java 中实现字符串高效匹配，关键不在“写对代码”，而在理解 next 数组的物理意义和匹配时指针移动的逻辑依据。它不是黑盒工具，而是用模式串自身结构“预判失败后该跳多远”的策略。
next 数组到底存什么
next[i] 表示：模式串从索引 0 到 i（含）这个子串中，最长相等真前缀与真后缀的长度。
注意两点：
- “真”前缀/后缀 ≠ 整个子串本身（比如 "abab" 的真前缀有 "a","ab","aba"；真后缀有 "b","ab","bab"）
- next[0] 固定为 0（单字符无真前后缀）
例如模式串 "ababc"：
-
i=0："a" → next[0] = 0 -
i=1："ab" → 前缀{"a"}，后缀{"b"} → 无公共 → next[1] = 0 -
i=2："aba" → 前缀{"a","ab"}，后缀{"a","ba"} → 公共 "a" → 长度 1 → next[2] = 1 -
i=3："abab" → 公共 "ab" → next[3] = 2 -
i=4："ababc" → 前缀{"a","ab","aba","abab"}，后缀{"c","bc","abc","babc"} → 无公共 → next[4] = 0
所以 next = [0, 0, 1, 2, 0]
构建 next 数组的 Java 实现（推荐版本）
public static int[] buildNext(String p) {
int n = p.length();
if (n == 0) return new int[0];
int[] next = new int[n];
next[0] = 0; // 第一个字符固定为0
int j = 0; // 当前最长公共前后缀长度，也作前缀末尾指针
for (int i = 1; i < n; i++) {
// 失配时回退：j > 0 且当前字符不匹配，就用 next[j-1] 缩小前缀范围
while (j > 0 && p.charAt(i) != p.charAt(j)) {
j = next[j - 1];
}
// 若匹配，j 扩展一位
if (p.charAt(i) == p.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}这个版本清晰体现“回退靠已有 next 值”，不是简单 j--，而是跳到上一级最长公共前缀的末尾继续比。
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
立即学习“Java免费学习笔记（深入）”；
KMP 匹配主过程（带位置返回）
public static int kmpSearch(String s, String p) {
if (p.isEmpty()) return 0;
int[] next = buildNext(p);
int i = 0, j = 0; // i: 主串指针，j: 模式串指针
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
if (j == 0) {
i++; // 模式串已退到头，主串必须进
} else {
j = next[j - 1]; // 利用已知结构，模式串回退
}
}
}
return j == p.length() ? i - j : -1; // 成功则返回起始下标，否则 -1
}核心逻辑：
- 匹配成功 → 双指针同步前进
- 失配且 j > 0 → j 回退到 next[j−1]，i 不动（主串绝不回溯）
- 失配且 j == 0 → i 单独前进，相当于模式串整体右移一位
容易踩坑的细节
- next 数组索引含义要统一：有的实现让 next[i] 对应 p[0..i−1]，有的对应 p[0..i]。本文采用 next[i] 对应子串 p[0..i]，匹配时用
next[j−1]回退，逻辑更直观。 - 字符串为空、模式串长度为 1 等边界情况需显式处理，避免数组越界。
- 不要混淆“最长公共前后缀长度”和“能跳几步”——next[j−1] 就是跳转目标位置（即新 j 值），不是偏移量。
不复杂但容易忽略：next 数组本质是模式串的“自相似指纹”，它把重复结构压缩成数字，让每次失配都能精准跳过已验证无效的尝试。
