第 11 章：搜索与字符串匹配 —— 字符串匹配

元数据卡： 难度进阶 | 前置二分搜索 | 关键词 Rabin-Karp·KMP·PMT·Trie·滚动哈希 | 预计阅读 50 分钟

你的进度： 你刚学会二分在有序数组定位。但数据不总是数字——你要在一段冒险日志里找「火焰行者」出现了多少次。暴力逐字比较 O(n×m)，大文本不可接受。

你的任务： 掌握 Rabin-Karp 滚动哈希降到 O(n+m)，了解 KMP 让 text 指针永不回头，以及 Trie 解决前缀查询。

朴素匹配

从 text 每个位置开始，和 pattern 逐字符比较。

java

// StringMatch.java — 朴素 + Rabin-Karp + KMP + Trie
public class StringMatch {
    // 朴素匹配 O(n×m)
    static int naiveSearch(String t, String p) {
        for (int i = 0; i <= t.length() - p.length(); i++) {
            int j = 0;
            while (j < p.length() && t.charAt(i + j) == p.charAt(j)) j++;
            if (j == p.length()) return i;
        }
        return -1;
    }

Rabin-Karp —— 滚动哈希

别比字符了，比较哈希值。滚动哈希让窗口移动时 O(1) 更新。

java

    // Rabin-Karp 滚动哈希 O(n+m) 平均
    static final int BASE = 256, MOD = 1_000_000_007;

    static int rkSearch(String t, String p) {
        int n = t.length(), m = p.length();
        if (m > n || m == 0) return -1;
        long patHash = 0, txtHash = 0, top = 1;
        for (int i = 0; i < m - 1; i++) top = (top * BASE) % MOD;
        for (int i = 0; i < m; i++) {
            patHash = (patHash * BASE + p.charAt(i)) % MOD;
            txtHash = (txtHash * BASE + t.charAt(i)) % MOD;
        }
        for (int i = 0; i <= n - m; i++) {
            if (patHash == txtHash && t.substring(i, i + m).equals(p)) return i;
            if (i < n - m) {
                txtHash = (txtHash - t.charAt(i) * top) % MOD;
                txtHash = (txtHash * BASE + t.charAt(i + m)) % MOD;
                if (txtHash < 0) txtHash += MOD;
            }
        }
        return -1;
    }

滚动原理：哈希 = ord('A')×BASE^2 + ord('A')×BASE + ord('B')。右移 = 移除最左字符贡献，整体左移（乘 BASE），加入新字符。O(1)。

KMP —— 不让 text 指针往回走（选读）

KMP 用 PMT 让 pattern 自己知道怎么退。例如 "ABABAC" → PMT = [0,0,1,2,3,0]。

java

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

text 指针永远向前，犯过的错靠 pattern 自己消化。

Trie —— 共享前缀的字典（选读）

HashSet 能回答单词是否存在，但回答不了「以 abc 开头」的单词。

java

    static class Trie {
        Trie[] ch = new Trie[26];  // 仅小写字母
        boolean end;
        void ins(String w) {
            Trie n = this;
            for (char c : w.toCharArray()) {
                if (n.ch[c - 'a'] == null) n.ch[c - 'a'] = new Trie();
                n = n.ch[c - 'a'];
            }
            n.end = true;
        }
        boolean has(String w) {
            Trie n = this;
            for (char c : w.toCharArray()) {
                if (n.ch[c - 'a'] == null) return false;
                n = n.ch[c - 'a'];
            }
            return n.end;
        }
        boolean pre(String p) {
            Trie n = this;
            for (char c : p.toCharArray()) {
                if (n.ch[c - 'a'] == null) return false;
                n = n.ch[c - 'a'];
            }
            return true;
        }
    }

    public static void main(String[] args) {
        String text = "AABAACAADAABAAABAA";
        String pat = "AABA";
        System.out.println("naive: " + naiveSearch(text, pat));     // 0
        System.out.println("rk:    " + rkSearch(text, pat));        // 0
        System.out.println("kmp:   " + kmpSearch("ABABABACABA", "ABABAC"));  // 2

        Trie trie = new Trie();
        for (String w : new String[]{"apple","app","application","banana"})
            trie.ins(w);
        System.out.println("trie.has(app): " + trie.has("app"));          // true
        System.out.println("trie.has(appl): " + trie.has("appl"));        // false
        System.out.println("trie.pre(app): " + trie.pre("app"));          // true
    }
}

javac StringMatch.java && java StringMatch
→ naive: 0
→ rk:    0
→ kmp:   2
→ trie.has(app): true
→ trie.has(appl): false
→ trie.pre(app): true

Trie 的操作都是 O(m)，和字典大小无关。代价是空间——每节点固定 208 字节。

选型指南

算法	适用场景	复杂度	特点
Rabin-Karp	单模式，长文本	O(n+m) 平均	简单，冲突时退化
KMP	单模式，流式处理	O(n+m) 确定	text 指针永不回溯
Trie	多模式，前缀查询	O(m) 每次	空间大，自动补全绝配

旅人笔记

哈希滚动省时间，PMT 不回头，Trie 前缀通天下。字符串匹配没有银弹——暴力法常数极小，短串场景反而是最优。

下一步

二分解决有序序列定位，字符串匹配解决文本定位。下一章跳出搜索，进入更高层次：分治与回溯。

→ 进入第 12 章：分治与回溯

← 回到第 11 章（二分搜索）

第 11 章：搜索与字符串匹配 —— 字符串匹配 ​

第 11 章：搜索与字符串匹配 —— 字符串匹配