本文介绍使用 KMP（Knuth–Morris–Pratt）算法高效查找子串在主串中所有匹配起始索引的方法，避免暴力或 indexOf() 带来的隐式高开销，确保整体时间复杂度严格为 O(N + M)，其中 N 为主串长度、M 为模式串长度。
本文介绍使用 kmp（knuth–morris–pratt）算法高效查找子串在主串中所有匹配起始索引的方法，避免暴力或 `indexof()` 带来的隐式高开销，确保整体时间复杂度严格为 o(n + m)，其中 n 为主串长度、m 为模式串长度。
在字符串匹配问题中，若需找出模式串 str1 在主串 str2 中所有出现的起始下标（如 "abc" 在 "abckdabcgfacabc" 中位于索引 0、5、12），朴素方法（逐位比对）或依赖 String.indexOf() 的实现（其内部仍是 O(N) 每次调用，叠加循环后退可能导致最坏 O(N×M)）均无法满足线性时间要求。
KMP 算法正是为此类问题设计的经典解决方案：它通过预处理模式串，构建部分匹配表（Partial Match Table，又称 failure function 或 LPS 数组），在匹配失败时跳过已知不可能成功的字符比较，从而将搜索阶段的时间复杂度降至 O(N)，预处理阶段为 O(M)，总时间复杂度为 O(N + M) ——当 M ≤ N 时，可简记为 O(N)。
✅ KMP 核心思想
- LPS 数组定义：lps[i] 表示模式串 needle[0..i] 的最长真前缀（proper prefix），同时也是其后缀的长度。例如 "abab" 的 LPS 数组为 [0,0,1,2]。
- 搜索过程：利用 LPS 在失配时回退模式串指针 k，而非主串指针 j，保证主串每个字符最多被访问一次。
? Java 实现（完整可运行）
import java.util.*;
public class KMPSearch {
// 构建 LPS 数组（长度为 pattern.length() + 1，便于边界处理）
static int[] computeLPS(String pattern) {
int n = pattern.length();
int[] lps = new int[n + 1];
lps[0] = -1; // 用于统一失配逻辑
int len = 0, i = 1;
while (i < n) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1]; // 回退到上一个可能匹配位置
} else {
lps[i] = 0;
i++;
}
}
}
lps[n] = len; // 最终值用于搜索终止判断
return lps;
}
// KMP 主搜索函数：返回所有匹配起始索引
static List<Integer> kmpSearch(String needle, String haystack) {
List<Integer> matches = new ArrayList<>();
int m = haystack.length();
int n = needle.length();
if (n == 0) return matches; // 空模式串，按需处理
if (n > m) return matches; // 模式串更长，直接无解
int[] lps = computeLPS(needle);
int i = 0, j = 0; // i: haystack index, j: needle index
while (i < m) {
if (needle.charAt(j) == haystack.charAt(i)) {
i++;
j++;
if (j == n) {
matches.add(i - j); // 找到一次匹配
j = lps[j - 1]; // 继续寻找重叠匹配（如 "aa" in "aaa" → [0,1]）
}
} else {
if (j != 0) {
j = lps[j - 1]; // 利用已知前缀信息跳转
} else {
i++; // 当前无匹配前缀，主串推进
}
}
}
return matches;
}
// 测试用例
public static void main(String[] args) {
System.out.println(kmpSearch("abc", "abckdabcgfacabc")); // 输出: [0, 5, 12]
System.out.println(kmpSearch("aa", "aaa")); // 输出: [0, 1]（支持重叠匹配）
System.out.println(kmpSearch("xyz", "abc")); // 输出: []
}
}⚠️ 注意事项与最佳实践
- 重叠匹配支持：上述实现默认支持重叠匹配（如 "aa" 在 "aaa" 中返回 [0, 1]）。若需非重叠匹配，匹配成功后令 j = 0 即可。
- 空串与边界处理：代码已显式处理 needle.length() > haystack.length() 和空串场景，避免无效计算。
- 空间复杂度：O(M)，仅需存储 LPS 数组，远优于暴力法的常数空间但时间不可控。
- 不适用场景：若仅需单次匹配且模式极短（如长度 ≤ 4），内置 indexOf() 可能因 JIT 优化而更快；但本题明确要求 O(N) 时间保障，KMP 是理论最优且工程可靠的选择。
综上，KMP 不仅满足题目对 O(N) 时间复杂度的硬性要求，还具备稳定性能、清晰逻辑和广泛适用性，是字符串多模式匹配问题的标准基石算法。
