11.2 字符串匹配
前置：二分搜索与哈希表。本页统一约定：空模式在任意文本中的首次位置为 0，未找到返回 -1；Java 下标按 UTF-16 代码单元计算。
日志不是有序数组
本页沿三条路线推进：
- 朴素匹配：保留最简单、最容易验证的基线；
- Rabin–Karp：用滚动哈希筛出候选窗口，再逐字确认；
- KMP：从模式自身计算失配后的跳转位置，让文本指针不回退。
最后的 Trie 解决的是另一类问题：不是在一段文本中寻找模式，而是在一组词中查询完整词或公共前缀。
一份可编译的实现
字符串参数必须非 null，否则抛出 NullPointerException。窗口循环用 start <= n-m，避免超长文本末端的 start+m 溢出。Trie 先检查完整输入，再访问或创建节点，非法后缀不会留下半条路径。
import java.util.Objects;
public final class StringMatchingDemo {
private static final long BASE = 65_536;
private static final long MOD = 1_000_000_007L;
private StringMatchingDemo() {}
static int naiveSearch(String text, String pattern) {
Objects.requireNonNull(text, "text");
Objects.requireNonNull(pattern, "pattern");
int n = text.length();
int m = pattern.length();
if (m == 0) {
return 0;
}
for (int start = 0; start <= n - m; start++) {
int matched = 0;
while (matched < m
&& text.charAt(start + matched) == pattern.charAt(matched)) {
matched++;
}
if (matched == m) {
return start;
}
}
return -1;
}
static int rabinKarp(String text, String pattern) {
Objects.requireNonNull(text, "text");
Objects.requireNonNull(pattern, "pattern");
int n = text.length();
int m = pattern.length();
if (m == 0) {
return 0;
}
if (m > n) {
return -1;
}
long highestPlace = 1;
long patternHash = 0;
long windowHash = 0;
for (int index = 0; index < m - 1; index++) {
highestPlace = highestPlace * BASE % MOD;
}
for (int index = 0; index < m; index++) {
patternHash = (patternHash * BASE + pattern.charAt(index)) % MOD;
windowHash = (windowHash * BASE + text.charAt(index)) % MOD;
}
for (int start = 0; start <= n - m; start++) {
if (windowHash == patternHash
&& text.regionMatches(start, pattern, 0, m)) {
return start;
}
if (start < n - m) {
long outgoing = text.charAt(start) * highestPlace % MOD;
windowHash = (windowHash - outgoing + MOD) % MOD;
windowHash = (windowHash * BASE + text.charAt(start + m)) % MOD;
}
}
return -1;
}
static int[] prefixFunction(String pattern) {
int[] prefix = new int[pattern.length()];
for (int index = 1, length = 0; index < pattern.length(); index++) {
while (length > 0
&& pattern.charAt(index) != pattern.charAt(length)) {
length = prefix[length - 1];
}
if (pattern.charAt(index) == pattern.charAt(length)) {
length++;
}
prefix[index] = length;
}
return prefix;
}
static int kmpSearch(String text, String pattern) {
Objects.requireNonNull(text, "text");
Objects.requireNonNull(pattern, "pattern");
if (pattern.isEmpty()) {
return 0;
}
int[] prefix = prefixFunction(pattern);
for (int textIndex = 0, matched = 0;
textIndex < text.length();
textIndex++) {
while (matched > 0
&& text.charAt(textIndex) != pattern.charAt(matched)) {
matched = prefix[matched - 1];
}
if (text.charAt(textIndex) == pattern.charAt(matched)) {
matched++;
if (matched == pattern.length()) {
return textIndex - matched + 1;
}
}
}
return -1;
}
static final class Trie {
private final Trie[] children = new Trie[26];
private boolean terminal;
void insert(String word) {
validate(word);
Trie node = this;
for (int index = 0; index < word.length(); index++) {
int slot = slot(word.charAt(index));
if (node.children[slot] == null) {
node.children[slot] = new Trie();
}
node = node.children[slot];
}
node.terminal = true;
}
boolean contains(String word) {
Trie node = findPrefix(word);
return node != null && node.terminal;
}
boolean startsWith(String prefix) {
return findPrefix(prefix) != null;
}
private Trie findPrefix(String value) {
validate(value);
Trie node = this;
for (int index = 0; index < value.length(); index++) {
node = node.children[slot(value.charAt(index))];
if (node == null) {
return null;
}
}
return node;
}
private static void validate(String value) {
for (int index = 0; index < value.length(); index++) {
slot(value.charAt(index));
}
}
private static int slot(char value) {
if (value < 'a' || value > 'z') {
throw new IllegalArgumentException(
"this trie accepts lowercase ASCII letters only");
}
return value - 'a';
}
}
public static void main(String[] args) {
String text = "AABAACAADAABAAABAA";
String pattern = "AABA";
assert naiveSearch(text, pattern) == 0;
assert rabinKarp(text, pattern) == 0;
assert kmpSearch(text, pattern) == 0;
assert naiveSearch("ABABABACABA", "ABABAC") == 2;
assert rabinKarp("ABABABACABA", "ABABAC") == 2;
assert kmpSearch("ABABABACABA", "ABABAC") == 2;
assert kmpSearch("abc", "") == 0;
assert rabinKarp("short", "longer") == -1;
Trie trie = new Trie();
trie.insert("app");
trie.insert("apple");
trie.insert("application");
assert trie.contains("app");
assert !trie.contains("appl");
assert trie.startsWith("appl");
assert trie.startsWith("");
System.out.println("三种匹配结果一致");
}
}运行：
javac StringMatchingDemo.java
java -ea StringMatchingDemo断言通过后输出 三种匹配结果一致。
Rabin–Karp：哈希命中仍要确认
长度为 m 的窗口哈希可写成：
c0 * BASE^(m-1) + c1 * BASE^(m-2) + ... + c(m-1)实际每一步都对 MOD 取模。窗口右移时，先减去最左代码单元的高位贡献，再乘 BASE，最后加入新代码单元。BASE=65536 对应整个 char 值域；本组常量的乘积在 long 范围内。对 0<m<=n，预处理模式与首个窗口为 O(m)，之后每次更新哈希为 O(1)。
不同字符串可能产生同一模哈希，所以哈希相等只能说明“值得核对”。代码用 regionMatches 逐字符确认，不会因碰撞返回错误答案。设遇到 c 个哈希相等的候选窗口，总上界为 O(n+m+c*m)；实际核对也可能提前遇到不同字符。只有进一步约定输入或哈希随机模型，并控制核对总成本，才能谈期望 O(n+m)。本例固定 BASE 与 MOD，没有随机化保证；最坏仍可到 O(nm)。对抗输入、密码或防篡改场景不能把这份教学滚动哈希当作安全摘要。
KMP：失配后保留多长前缀
对模式 ABABAC，前缀函数是：
pattern: A B A B A C
prefix: 0 0 1 2 3 0prefix[i] 表示 pattern[0..i] 的最长真前缀长度，同时这个前缀也是后缀。若已经匹配 matched 个字符却在下一个位置失配，不必让文本指针回退；把 matched 改成 prefix[matched-1]，继续检查仍可能成立的较短边界。
构造前缀函数和扫描文本都具有同样的“指针只前进、失败长度逐步缩短”结构，总时间是 O(n+m)，额外空间 O(m)。每次成功比较最多把已匹配长度增加 1，每次回退又严格减小它，回退总量受此前增加量限制。这是线性分析的依据；内层 while 并不自动意味着二次时间。KMP 的优势是确定性线性界，不是保证在每个短字符串上都比标准库快。
Trie：前缀查询是另一份合同
Trie 把词拆成边，共享公共前缀。contains("app") 要求路径存在且终点标记为完整词；startsWith("app") 只要求路径存在。这两个判断不能混用。
本页为了把索引关系写清，只接受 a..z，每个节点固定保存 26 个孩子引用。它先验证整串，所以即使开头就无匹配，查询也要 O(m+1) 时间；m 是输入词长度。若所有插入词合计 L 个字符，节点数至多 L+1，包括始终存在的根。每个节点 26 个槽，存储为 Θ(26P)，P 为实际前缀节点数；26 固定时也写作 Θ(P)。实际字节数受 JVM、对象头、引用宽度与对齐影响，不能从“26 个槽”推导出一个跨环境固定数字。字符集很大或分支稀疏时，映射可避免为不存在的分支预留整排槽位，但会引入哈希、容器对象和不同的访问常数。不能不看分支密度就断言一定更省。
空前缀始终存在，即使还没插入任何词，startsWith("") 也返回 true；contains("") 则只有在插入空词后才为 true。重复插入不会产生额外词记录。非法字符会统一抛出 IllegalArgumentException，不因前缀碰巧不存在就提前返回 false。
Java char 是 UTF-16 代码单元。例如文本 "😀x" 中 x 的 Java 下标是 2，不是码点下标 1。若产品合同按 Unicode 码点、用户感知字符或规范化文本匹配，需要先统一编码与规范化策略，不能把 charAt 下标直接当作所有语言中的“字符位置”。
复杂度与选择
| 方法 | 时间 | 额外空间 | 适合的问题 |
|---|---|---|---|
| 朴素匹配 | 最坏 O(nm) | O(1) | 短模式、基线验证 |
| Rabin–Karp | O(n+m+c*m)，c 为哈希候选数；最坏 O(nm) | O(1) | 滚动窗口、多模式哈希扩展 |
| KMP | O(n+m) | O(m) | 单模式、流式或确定性线性要求 |
| Trie | 每次 O(m+1) | 存储 Θ(P)；查询辅助 O(1) | 词典、前缀查询 |
空模式在三个搜索中均为常数时间；模式长于文本时朴素法与 Rabin–Karp 直接失败，KMP 仍会先建模式前缀表。本页 KMP 接收完整 String；流式版本还需跨输入块保存 matched 和累计位置。可参照 Princeton 子串查找与 Trie资料。
工程代码应优先明确标准库的语义和性能边界。Java String.indexOf 已提供子串查找；算法页面的价值在于理解何时能复用工作，而不是要求业务代码重复实现。
动手验证失配与前缀
- 手算
AAAA、ABABAC与aabaaab的前缀函数。 - 为三种搜索生成随机短字符串，与
String.indexOf对照。 - 构造一个很小模数的 Rabin–Karp，主动制造哈希碰撞，确认逐字核对仍能拒绝假命中。
- 给 Trie 增加删除。共享前缀节点在什么条件下才能回收？
- 若要支持大小写不敏感的 Unicode 文本，输入合同还缺哪些规范化步骤？
朴素匹配提供最容易信任的基线；Rabin–Karp 以哈希筛选候选，但必须核对碰撞；KMP 把模式中已经知道的前后缀关系写进跳转表；Trie 则把问题从“文本中找模式”换成“词典中查前缀”。