字符串算法：从匹配到自动机

这篇来自我补“字符串算法：从匹配到自动机”基础时的一次复盘。我之前的问题是：字符串匹配从朴素算法跳到 KMP、Trie 和自动机时，我一度只看到越来越多的数组和指针，看不到它们复用了哪部分信息。等我把输入、状态变化和边界条件分别写出来之后，原来看似突然出现的规则就有了来路。

字符串算法经常让人觉得抽象：KMP、Rabin-Karp、Trie、AC 自动机、Manacher、后缀数组……名字很多，图也容易画乱。

但如果抓住主线，它们其实都围绕一个问题：如何更高效地比较字符串、匹配模式、复用前缀信息。

字符串算法路线

图：字符串算法从逐位比较，逐步走向前缀复用和自动机

常见字符串问题可以分成几类：

问题	常见算法
单模式匹配	暴力匹配、KMP、Rabin-Karp
多模式匹配	Trie、AC 自动机
回文	中心扩展、Manacher
子串比较	字符串哈希、后缀数组
编辑转换	编辑距离 DP
前缀统计	Trie、前缀函数、Z 函数

暴力匹配

最直接的字符串匹配是逐个起点尝试：

int indexOfBruteForce(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
            j++;
        }
        if (j == m) return i;
    }
    return -1;
}

最坏复杂度是 O(nm)。如果文本和模式串都很长，并且存在大量重复前缀，性能会很差。

Rabin-Karp：用哈希比较子串

Rabin-Karp 的思路是给字符串窗口计算哈希值。如果窗口哈希和模式串哈希不同，一定不匹配；如果相同，再做一次字符确认，避免哈希冲突。

它适合多模式、重复查询和大文本扫描场景。

核心思想：

hash(text[i..i+m-1]) 可以从上一个窗口 O(1) 滚动得到

工程里使用字符串哈希一定要承认冲突存在。不能把哈希相等当作字符串一定相等，除非业务允许极小概率误判。

KMP：失配时不回到起点

KMP 解决的问题是：当模式串匹配到一半失败时，不要把文本指针回退，而是利用模式串自己的前后缀信息跳转。

它的关键是前缀函数，也常被叫做 next 数组。next[i] 描述的是模式串前 i 个字符中，最长相等真前缀和真后缀长度。

简化实现：

int[] buildNext(String p) {
    int[] next = new int[p.length()];
    for (int i = 1, j = 0; i < p.length(); i++) {
        while (j > 0 && p.charAt(i) != p.charAt(j)) {
            j = next[j - 1];
        }
        if (p.charAt(i) == p.charAt(j)) j++;
        next[i] = j;
    }
    return next;
}

int kmp(String text, String pattern) {
    if (pattern.isEmpty()) return 0;
    int[] next = buildNext(pattern);
    for (int i = 0, j = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) j++;
        if (j == pattern.length()) return i - j + 1;
    }
    return -1;
}

KMP 的难点不是代码，而是理解“失配后模式串该跳到哪里”。跳转依据来自模式串已经匹配部分的最长公共前后缀。

Trie：把前缀变成路径

Trie 适合处理大量字符串的前缀查询。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean end;
}

插入单词时，每个字符走一条边；查询前缀时，从根沿路径走即可。

Trie 的优势是前缀共享，缺点是节点多、空间大。工程中遇到中文、Unicode 或任意字符集时，数组孩子不一定合适，可能需要 Map<Character, TrieNode>，或者使用压缩 Trie。

AC 自动机：多模式匹配

如果要在一篇文章里同时查很多敏感词，用每个词跑一遍 KMP 会很浪费。AC 自动机把很多模式串放进 Trie，再加失败指针，让扫描文本时可以一次性匹配多个模式。

它适合：

敏感词检测。
多关键词扫描。
安全规则匹配。
日志模式识别。

理解 AC 自动机时要区分两种边：

Trie 边：真实字符路径。
fail 边：匹配失败时跳转到哪里。

这两种线画混了，图就会变得非常难读。

回文算法

回文问题最常见是中心扩展：

String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);
        int len2 = expand(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start + 1) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--; r++;
    }
    return r - l - 1;
}

中心扩展是 O(n²)，Manacher 可以做到 O(n)，但实现更复杂。学习时建议先把中心扩展写稳，再看 Manacher 如何复用回文半径。

常见错误

KMP 的 next 数组含义没定义清楚。
文本指针和模式指针同时回退，导致复杂度退化。
字符串哈希不处理冲突。
Trie 默认只支持小写字母，却直接用于中文或任意字符。
回文没有区分奇数长度和偶数长度。
多模式匹配用循环跑单模式算法，规模上来后性能不稳。

工程场景

搜索关键词高亮。
敏感词过滤。
代码编辑器查找。
日志规则匹配。
拼写提示和自动补全。
URL 路由匹配。
DNA 序列匹配。

字符串算法在工程里经常和编码、大小写、Unicode、分词结合。中文场景不能简单按英文字符模型处理，尤其是关键词匹配、搜索和高亮。

面试题

KMP 的 next 数组到底保存什么？
Rabin-Karp 为什么需要二次字符确认？
Trie 为什么适合前缀查询？
AC 自动机和 Trie 的关系是什么？
最长回文子串和最长回文子序列有什么区别？

小结

字符串算法的主线是复用信息：哈希复用窗口摘要，KMP 复用前后缀，Trie 复用前缀路径，AC 自动机复用多模式状态。学它们时不要只背名称，要把“失配后怎么走、状态代表什么、是否允许误判”讲清楚。