经典算法专栏 #08：字符串算法

字符串匹配的核心矛盾是：暴力法每次失配都"忘记"已知信息，从头再来。KMP、BM、RK 各自用不同方式记住已比较的信息，避免冗余工作。本文不止给代码——重点讲清每个算法为什么这样跳跃是安全的。对应《算法导论》第 32 章。

目录

暴力法的瓶颈

暴力法每次失配，文本指针回退，已比较的信息全部丢弃：

T: a b a b a b c a b a b a b c
P: a b a b a b c

i=0: a b a b a b c  全部匹配！找到位置 0
i=1: a b a b a...  失配于 'b' vs 'c'，回退 i=1，j=0
...
每次都从 j=0 重新开始，浪费了"ab"已经匹配的信息

最坏情况：T="aaa...a"(n), P="aaa...ab"(m)，每次比到最后才发现不匹配，O(nm)。

KMP：利用模式串自身信息

核心直觉

KMP 的关键洞察：失配时，模式串已匹配的前缀可能与它自己的某个后缀重合——这个重合部分不需要重新匹配，直接从重合处继续。

T: a b a b c a b a b a b c
P: a b a b c

匹配到 T[4]='c', P[4]='c' ✅，但 T[5]='a', P[5] 不存在，
已匹配 "a b a b"。
P 的前缀 "a b" = P 的后缀 "a b"（fail[3]=2）
→ 模式串直接跳到 j=2，无需从 j=0 重来！

fail 数组：手推完整过程

fail[j] = P[0..j] 中，最长真前缀同时也是后缀的长度。

以 P = "a b a b a c" 为例，逐步推导：

最终 fail = [0, 0, 1, 2, 3, 0]

构建算法的双指针含义：

int[] buildFail(String p) {
    int m = p.length();
    int[] fail = new int[m];
    int k = 0;  // k = 当前已知最长公共前后缀的长度
    for (int i = 1; i < m; i++) {
        // p[k] 是"候选前缀"的下一个字符
        // p[i] 是当前后缀的末尾字符
        while (k > 0 && p.charAt(i) != p.charAt(k))
            k = fail[k - 1];  // 缩短候选前缀，退到上一个可能的匹配
        if (p.charAt(i) == p.charAt(k))
            k++;              // 候选前缀延长一位
        fail[i] = k;
    }
    return fail;
}

为什么 while 里用 fail[k-1] 而不是 k-1？

假设 fail[i] 候选 k 失败了（p[i] ≠ p[k]），
需要找下一个可能的公共前后缀长度。
P[0..k-1] 是已知的最长公共前后缀，
fail[k-1] 是 P[0..k-1] 自身的最长公共前后缀，
→ 这就是比 k 更短的下一个候选长度。

完整匹配例题

T = "a b c a b c a b d", P = "a b c a b d"

fail = [0, 0, 0, 1, 2, 0]

i=0, j=0: T[0]='a'=P[0]='a', j=1
i=1, j=1: T[1]='b'=P[1]='b', j=2
i=2, j=2: T[2]='c'=P[2]='c', j=3
i=3, j=3: T[3]='a'=P[3]='a', j=4
i=4, j=4: T[4]='b'=P[4]='b', j=5
i=5, j=5: T[5]='c' ≠ P[5]='d'，失配！
          j = fail[4] = 2
          T[5]='c'=P[2]='c', j=3
i=6, j=3: T[6]='a'=P[3]='a', j=4
i=7, j=4: T[7]='b'=P[4]='b', j=5
i=8, j=5: T[8]='d'=P[5]='d', j=6 → j==m，匹配！位置 = 8-6+1 = 3

结果：P 在 T 的位置 3 处匹配 ✅

List<Integer> kmpMatch(String t, String p) {
    int n = t.length(), m = p.length();
    int[] fail = buildFail(p);
    List<Integer> result = new ArrayList<>();
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && t.charAt(i) != p.charAt(j))
            j = fail[j - 1];
        if (t.charAt(i) == p.charAt(j)) j++;
        if (j == m) {
            result.add(i - m + 1);
            j = fail[j - 1];  // 继续找下一个，不从 0 重来
        }
    }
    return result;
}
// 时间 O(n+m)：i 单调递增 O(n)，j 的增减总次数 ≤ n → 总 O(n)
// 构建 fail O(m)，总体 O(n+m)，空间 O(m)

Boyer-Moore：从右往左，大步跳跃

两条规则的直觉

BM 的核心反直觉：从模式串右端向左比较——这样一旦发现不匹配，可以利用"文本中出现了什么字符"做最大跳跃。

坏字符规则（Bad Character）：

T: ...X...
P:  ...Y...  ← Y 与 T 中对齐位置的字符 X 不匹配

X 称为"坏字符"：
  情况1：X 在 P 中不存在 → P 整体跳过 X（跳 m 步）
  情况2：X 在 P 中存在，最右位置 r → 将 P[r] 对齐 T 中的 X（跳 j-r 步）
  情况3：计算得跳步 ≤ 0 时，至少跳 1 步（防止回退）

好后缀规则（Good Suffix）：

T: ...BCBC...
P:  ABCBC    ← 已匹配后缀 "CBC"

在 P 的其他位置找 "CBC"：
  若找到 P[1..3]="CBC" → 对齐它
  若找不到 → 找 P 的最长前缀与 "CBC" 的后缀匹配
  若都没有 → 跳过整个 P

实际实现中取两条规则的最大跳步：shift = max(badCharShift, goodSuffixShift)

完整例题：BM 匹配过程

T = "HERE IS A SIMPLE EXAMPLE", P = "EXAMPLE"（长度 7）

预处理坏字符表（记录每个字母最右出现位置）：

E→6, X→1, A→4, M→3, P→2, L→5, 其他→-1

对齐 T[0..6] vs P[0..6]，从右往左比较：
  T[6]='S', P[6]='E'，不匹配
  坏字符 'S' 不在 P 中 → 跳 7 步
  （好后缀 "" 为空，跳 0 步，取 max(7,0)=7）

对齐 T[7..13]='IS A SIM' vs P，从右比较：
  T[13]='M', P[6]='E'，不匹配
  坏字符 'M' 在 P 中位置 3，当前 j=6 → 跳 6-3=3 步

对齐 T[10..16]='SIMPLE ' vs P，从右比较：
  T[16]=' ', P[6]='E'，不匹配
  坏字符 ' ' 不在 P → 跳 7 步

对齐 T[17..23]='EXAMPLE' vs P：
  T[23]='E'=P[6] ✅
  T[22]='L'=P[5] ✅
  T[21]='P'=P[4] ✅
  T[20]='M'=P[3] ✅
  T[19]='A'=P[2] ✅
  T[18]='X'=P[1] ✅
  T[17]='E'=P[0] ✅ → 完全匹配！位置 17

总比较次数约 15 次，而暴力法需要约 4×7=28 次。

为什么 BM 平均次线性：大字符集（26个字母）下，坏字符几乎总是不在模式串中（P 只用了少数字母），每次平均跳 m 步，总比较约 n/m 次。

Rabin-Karp：哈希比较

滚动哈希原理

把长度为 m 的字符串看成 m 位的 d 进制数（d 为字符集大小），用多项式哈希：

h("abc") = a·d² + b·d + c  （mod q，q 为大素数）

滚动更新（窗口右移一步）：

h(T[1..m]) = d · (h(T[0..m-1]) - T[0]·d^(m-1)) + T[m]  (mod q)
             ↑去掉最左字符              ↑加入新字符
每次 O(1)，无需重新计算

完整例题

T = "2359023141526739921", P = "31415", d=10, q=13

预计算：h(P) = 3·10⁴ + 1·10³ + 4·10² + 1·10 + 5 = 31415 mod 13 = 7

初始窗口 T[0..4]="23590"：h = 23590 mod 13 = 8 ≠ 7
滚动到 T[1..5]="35902"：h = (10·(8 - 2·10000) + 2) mod 13 = 3 ≠ 7
...
T[6..10]="31415"：h = 7 = h(P) → 逐字符验证 "31415"="31415" ✅ 匹配！

List<Integer> rabinKarp(String t, String p, int d, int q) {
    int n = t.length(), m = p.length();
    long h = 1;
    for (int i = 0; i < m - 1; i++) h = (h * d) % q;  // d^(m-1) mod q

    long ph = 0, th = 0;
    for (int i = 0; i < m; i++) {
        ph = (d * ph + p.charAt(i)) % q;
        th = (d * th + t.charAt(i)) % q;
    }
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i <= n - m; i++) {
        if (ph == th && t.regionMatches(i, p, 0, m))  // 哈希相等再验证
            result.add(i);
        if (i < n - m)
            th = (d * (th - t.charAt(i) * h % q + q) + t.charAt(i + m)) % q;
    }
    return result;
}

哈希碰撞的处理

假阳性：两个不同字符串哈希值相同，导致不必要的验证。

解决方案：

1. 选大素数 q：碰撞概率约 1/q，q=10⁹+7 时极低
2. 双哈希：同时用两个不同的 (d, q) 对，两个都相等才验证，碰撞概率降到约 1/q²
3. 逐字符验证：哈希匹配时再做 O(m) 验证（已在代码中实现）

多模式匹配优势

同时搜索 k 个长度相同的模式串：

预处理：将 k 个模式串的哈希值存入 HashSet
匹配时：每个窗口哈希 O(1) 查 HashSet，命中才验证
总时间 O(n + km)（比 k 次 KMP 的 O(kn) 快 k 倍）

Trie 树：前缀的力量

结构直觉

将一组字符串的公共前缀合并存储，每个节点代表一个字符前缀：

插入 ["apple", "app", "apply", "apt"]：

        root
         |
         a
         |
         p
        / \
       p   t
      / \    \
     l   (end) (end)
    / \
   e   y
  (end)(end)

"apple"和"apply"共享前缀"appl"，节省了存储。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
    int count;  // 可选：记录以此节点为前缀的单词数
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {           // O(m)
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null)
                node.children[i] = new TrieNode();
            node = node.children[i];
            node.count++;
        }
        node.isEnd = true;
    }

    boolean search(String word) {        // O(m)
        TrieNode node = getNode(word);
        return node != null && node.isEnd;
    }

    boolean startsWith(String prefix) {  // O(m)
        return getNode(prefix) != null;
    }

    // 统计以 prefix 为前缀的单词数
    int countPrefix(String prefix) {     // O(m)
        TrieNode node = getNode(prefix);
        return node == null ? 0 : node.count;
    }

    private TrieNode getNode(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }
}

空间优化：压缩 Trie（Radix Tree）

当节点只有一个子节点时，可将路径压缩为边上的字符串：

普通 Trie（"application"）：
  root → a → p → p → l → i → c → a → t → i → o → n

压缩 Trie（Radix Tree）：
  root → "application"   （10 个单字符节点压缩为 1 条边）
节省 90% 的节点

Java 中 java.util.concurrent.ConcurrentHashMap 的某些实现使用了类似压缩 Trie 的结构。

典型应用

AC 自动机：多模式的 KMP

为什么需要 AC 自动机

Trie 能表示多个模式串，但匹配时一旦失败，不知道跳到哪里继续，只能回到根重来——等价于多次 KMP，O(n × 平均模式长度)。

AC 自动机在 Trie 上加入 fail 链（类比 KMP 的 fail 数组），使失配时不用回根，直接跳到最长可能匹配的状态。

构建 fail 链：BFS 层序

fail 链含义：当前节点代表的字符串，其最长真后缀在 Trie 中对应的节点。

void buildFail(TrieNode root) {
    Queue<TrieNode> queue = new LinkedList<>();
    for (int i = 0; i < 26; i++) {
        if (root.children[i] != null) {
            root.children[i].fail = root;
            queue.offer(root.children[i]);
        } else {
            root.children[i] = root;  // 根的空子节点指向自身（goto 优化）
        }
    }
    while (!queue.isEmpty()) {
        TrieNode cur = queue.poll();
        // cur 代表字符串 s，cur.fail 代表 s 的最长真后缀
        for (int i = 0; i < 26; i++) {
            TrieNode child = cur.children[i];
            if (child == null) {
                // goto 压缩：失配时直接跳到 fail 链上对应的子节点
                cur.children[i] = cur.fail.children[i];
            } else {
                child.fail = cur.fail.children[i];
                queue.offer(child);
            }
        }
    }
}

完整例题：敏感词过滤

模式串集合：{"he", "she", "his", "hers"}，文本："ushers"

建 Trie（fail 链省略，用箭头表示 goto）：

graph TD
    root --> h1["h"]
    root --> s1["s"]
    h1 --> e1["e（he✓）"]
    h1 --> i1["i"]
    s1 --> h2["h"]
    e1 --> r1["r"]
    i1 --> s2["s（his✓）"]
    r1 --> s3["s（hers✓）"]
    h2 --> e2["e（she✓）"]

匹配过程（文本 "ushers"）：

读 'u'：root → goto 失败 → 回 root（根的 goto u = root 自身）
读 's'：root → s1
读 'h'：s1 → h2
读 'e'：h2 → e2（"she" 匹配！）
         e2.fail = e1（"he" 也匹配！输出）
读 'r'：e2 → ? 无子节点，goto e1.fail.children['r'] → r1
         e2.fail → e1 → r1
读 's'：r1 → s3（"hers" 匹配！）

一次扫描，找到：she(pos=2), he(pos=2), hers(pos=2..5)

List<String> search(String text) {
    List<String> result = new ArrayList<>();
    TrieNode cur = root;
    for (int i = 0; i < text.length(); i++) {
        int c = text.charAt(i) - 'a';
        cur = cur.children[c];          // goto 压缩后不会 null
        TrieNode tmp = cur;
        while (tmp != root) {           // 沿 fail 链收集所有匹配
            if (tmp.isEnd) result.add(tmp.word);
            tmp = tmp.fail;
        }
    }
    return result;
}
// 总时间 O(n + m_total + matches)，一次扫描完成

生产实践：美团、微信等平台的敏感词过滤系统，核心就是 AC 自动机。模式串（违禁词列表）提前构建自动机，每条消息 O(n) 扫描一遍。

算法选型

flowchart TD
    A{"单模式还是多模式？"} -->|单模式| B{"文本/模式特征"}
    A -->|多模式 k 个| C{"k 的大小"}

    B -->|通用场景| E["KMP<br/>O(n+m)，实现简单，教科书首选"]
    B -->|长模式 + 大字符集| F["Boyer-Moore<br/>平均 O(n/m)，grep 的选择"]
    B -->|多次搜索不同模式| G["Rabin-Karp<br/>预处理 O(m)，多模式扩展性好"]

    C -->|k ≤ 10| H["k 次 KMP<br/>O(kn)，简单直接"]
    C -->|10 < k ≤ 1000| I["Rabin-Karp 多模式<br/>O(n + km)，长度相同时最优"]
    C -->|k > 1000<br/>（如敏感词库）| J["AC 自动机<br/>O(n + m_total)，最优"]

    style E fill:#d5e8d4,stroke:#82b366
    style F fill:#d5e8d4,stroke:#82b366
    style J fill:#d5e8d4,stroke:#82b366

参考资料

• 《算法导论》（CLRS）第 3 版 — 第 32 章字符串匹配
• 《算法》（Sedgewick）— 第 5 章字符串
• Aho & Corasick 原论文（1975）— "Efficient String Matching"
• 基础数据结构（Trie 的节点结构与哈希表在 Rabin-Karp 多模式中的应用）
• 算法复杂度分析（KMP O(n+m) 的摊还分析：j 增减次数各不超过 n）