如何在线性时间复杂度 O(N) 内查找子串在主串中的全部起始位置

本文详解如何使用 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 < 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++;            }        }    }    return lps;}static List<Integer> 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 < m) {        if (pattern.charAt(j) == text.charAt(i)) {            i++;            j++;        }        if (j == n) {            result.add(i - j); // 找到一次匹配，记录起始索引            j = lps[j - 1];   // 继续寻找下一个匹配（支持重叠匹配，如 "aaa" in "aaaa" → [0,1,2]）        } else if (i < m && pattern.charAt(j) != text.charAt(i)) {            if (j != 0) {                j = lps[j - 1];            } else {                i++;            }        }    }    return result;}

? 关键设计说明：

• computeLPS() 正确计算最长公共前后缀长度数组（比维基伪代码更直观且广泛验证）；
• kmpSearch() 支持重叠匹配（如模式 "aa" 在 "aaa" 中应返回 [0, 1]），若需非重叠匹配，可在找到后令 j = 0；
• 提前判断 n > m 可避免无效建表，强化 O(N) 实际表现。

⚠️ 注意事项

• KMP 不适用于极短模式（如长度 ≤ 3），此时内置 indexOf() 可能因 JIT 优化反而更快；
• 若业务场景需忽略大小写或支持通配符，KMP 需扩展（如结合 Boyer-Moore 或改用 Aho-Corasick）；
• 注意 lps 数组索引与含义：lps[i] 对应 pattern[0..i]，而非 pattern[0..i-1]，确保边界安全。

✅ 总结

KMP 是解决「多位置精确子串匹配」的标准线性算法。相比调用 indexOf() 的试探性切片方案，它具备严格可证明的时间上界、无隐藏循环嵌套、且工程实现成熟稳定。对于中长模式串或高频匹配场景（如日志分析、DNA 序列扫描），采用 KMP 能显著提升吞吐量并保障响应确定性。