本文详解如何使用 KMP（Knuth-Morris-Pratt）算法在 O(N + M) 时间内高效找出模式串在文本串中所有匹配的起始索引，避免暴力或 indexOf() 带来的隐式高开销，真正实现接近 O(N) 的线性搜索性能。
本文详解如何使用 kmp（knuth-morris-pratt）算法在 o(n + m) 时间内高效找出模式串在文本串中所有匹配的起始索引，避免暴力或 `indexof()` 带来的隐式高开销，真正实现接近 o(n) 的线性搜索性能。
在字符串匹配问题中，若需找出模式串 str1 在主串 str2 中所有出现位置的起始下标（如 "abc" 在 "abckdabcgfacabc" 中返回 [0, 5, 12]），朴素方法（双重循环）或依赖 String.indexOf() 的实现均无法保证整体 O(N) 时间复杂度——因为 indexOf() 底层仍是 O(N) 子串扫描，多次调用将退化为 O(N×M)。
KMP 算法正是为此而生：它通过预处理模式串构建「部分匹配表」（又称 failure function 或 prefix function），在匹配失败时跳过已知不可能匹配的位置，从而消除回溯，实现单次遍历主串的线性时间搜索。
✅ KMP 的时间复杂度优势
- 构建部分匹配表：O(M)，M 为模式串长度
- 主串匹配过程：O(N)，N 为主串长度
- 总体时间复杂度：O(N + M)，当 M ≤ N（常见场景）时，可视为 O(N)
- 空间复杂度：O(M)，仅需存储长度为 M+1 的匹配表
? Java 实现要点解析
以下为完整、健壮的 KMP 实现（含边界处理与逻辑注释）：
static int[] computeLPS(String pattern) {
int n = pattern.length();
int[] lps = new int[n]; // lps[i] 表示 pattern[0..i] 的最长真前缀同时也是后缀的长度
int len = 0; // 当前最长匹配前缀长度
int i = 1;
while (i kmpSearch(String pattern, String text) {
List<integer> result = new ArrayList();
int m = text.length();
int n = pattern.length();
if (n == 0) return result; // 空模式串，按约定返回所有位置或空（此处返回空）
if (n > m) return result; // 模式串更长，无匹配可能
int[] lps = computeLPS(pattern);
int i = 0; // text 的索引
int j = 0; // pattern 的索引
while (i <blockquote>
<p>? <strong>关键设计说明</strong>： </p>
<ul>
<li>computeLPS() 正确计算最长公共前后缀长度数组（比维基伪代码更直观且广泛验证）； </li>
<li>kmpSearch() 支持<strong>重叠匹配</strong>（如模式 "aa" 在 "aaa" 中应返回 [0, 1]），若需非重叠匹配，可在找到后令 j = 0； </li>
<li>提前判断 n > m 可避免无效建表，强化 O(N) 实际表现。</li>
</ul>
</blockquote>
<h3>⚠️ 注意事项</h3>
<ul>
<li>KMP 不适用于极短模式（如长度 ≤ 3），此时内置 indexOf() 可能因 JIT 优化反而更快； </li>
<li>若业务场景需忽略大小写或支持通配符，KMP 需扩展（如结合 Boyer-Moore 或改用 Aho-Corasick）； </li>
<li>注意 lps 数组索引与含义：lps[i] 对应 pattern[0..i]，而非 pattern[0..i-1]，确保边界安全。</li>
</ul>
<h3>✅ 总结</h3>
<p>KMP 是解决「多位置精确子串匹配」的标准线性算法。相比调用 indexOf() 的试探性切片方案，它具备严格可证明的时间上界、无隐藏循环嵌套、且工程实现成熟稳定。对于中长模式串或高频匹配场景（如日志分析、DNA 序列扫描），采用 KMP 能显著提升吞吐量并保障响应确定性。</p></integer>
