外观
24 - 字符串匹配:从暴力查找到 KMP 的前缀复用
前置阅读:A - 算法正确性、测试与基准方法。
前缀索引见15 - Trie 前缀树;多个模式串的工程匹配不能直接等同于单模式 KMP。
摘要
在一段文本中查找一个固定字符串,要求找到的字符连续出现。待搜索的内容称为文本串,要寻找的字符串称为模式串。本文返回第一次命中的起始下标,找不到时返回 -1,空模式返回 0。
暴力匹配从每个可能的起点重新比较;KMP 利用模式串内部的前后缀关系,保留已匹配的信息,避免重复扫描文本。下面先解释这些信息是什么,再推导 LPS 数组和匹配过程,最后讨论流式输入与工程边界。
1. 重复比较从哪里来
文本 aaaaab 匹配模式 aaaab 时,从文本下标 0 开始,前四个 a 相等,但模式末尾的 b 与文本下标 4 的 a 不等,这称为失配。暴力算法把起点移到下标 1,从模式头部重新比较,最终命中。第二轮比较的多个 a 在第一轮已经读过。
KMP(Knuth-Morris-Pratt)的思路是:失配前已经知道文本中的一段等于模式前缀,若这段的末尾又等于模式的某个较短前缀,就能保留这部分匹配。上例已经匹配的 aaaa,末尾三个 a 等于模式开头三个 a,因此可以保留匹配长度 3,直接用当前文本字符继续比较。记录这种重合关系的就是 LPS 数组。
2. LPS 数组
前缀是从字符串开头取出的连续片段,后缀是到字符串末尾结束的连续片段;“真”表示不能取整个字符串自身。前后缀可以重叠,例如 aaaa 的最长相等真前后缀是 aaa,长度为 3。
LPS 是 Longest Proper Prefix which is also Suffix 的缩写。lps[i] 表示模式片段 pattern[0..i](包含下标 i)的最长相等真前后缀长度,没有非空候选时为 0。它只依赖模式串,不依赖文本。
构建时,i 是待计算的位置,length 是正在尝试扩展的前后缀长度:
pattern[i] == pattern[length]:旧的相等前后缀可以各接上一个相等字符,所以长度加一,并计算下一位置。- 字符不等且
length > 0:当前候选不能扩展,改试它自身的最长相等真前后缀,即lps[length - 1]。i不动,因为这个字符还没有找到可接续的候选。 - 字符不等且
length == 0:连模式首字符都接不上,当前位置的 LPS 为0,才能继续前进。
每次回退都缩短候选,可能需要连续回退多次。下面是 Java 方法片段,需放入类中使用;第 4 节给出完整类。
java
static int[] buildLps(String pattern) {
int[] lps = new int[pattern.length()];
int length = 0;
for (int i = 1; i < pattern.length(); ) {
if (pattern.charAt(i) == pattern.charAt(length)) {
lps[i++] = ++length;
} else if (length > 0) {
length = lps[length - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}3. 匹配实现
i 指向下一个待比较的文本位置,j 同时表示已匹配的模式前缀长度和下一个模式下标。循环开始时,文本中紧邻 i 之前的 j 个字符,等于模式的前 j 个字符。
字符相等时,两个下标一起前进;失配且 j > 0 时,令 j = lps[j - 1],保留已经确认相等的后缀,再与同一个文本字符比较;只有 j == 0 仍失配时,才跳过这个文本字符。第 5 节进一步说明为什么这种回退不会漏掉候选。
java
static int indexOf(String text, String pattern) {
if (pattern.isEmpty()) return 0;
int[] lps = buildLps(pattern);
int i = 0;
int j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
if (j == pattern.length()) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}设文本长度为 n、模式长度为 m。构建 LPS 为 O(m),匹配为 O(n),总时间 O(n+m),额外空间为 O(m)。这里按 Java char 计数,线性复杂度的理由见第 4.2 节。代码在 j == m 时返回 i - j,因此只返回第一次命中。
4. 完整可运行示例:暴力匹配与 KMP 对照
以下类只依赖 Java 标准库,可保存为 StringMatchDemo.java,用本地 JDK 编译运行。bruteForce 与 kmp 要求两个输入非 null,否则抛出空指针异常;空字符串是合法输入。第 2、3 节是核心方法片段,第 3 节片段没有完整类中的显式非空检查,调用前也应保证输入非 null。
java
import java.util.Objects;
/**
* 可运行示例:字符串匹配:从暴力查找到 KMP 的前缀复用。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class StringMatchDemo {
static int bruteForce(String text, String pattern) {
Objects.requireNonNull(text);
Objects.requireNonNull(pattern);
if (pattern.isEmpty()) return 0;
// i 是本轮尝试的文本起点;最晚起点必须还能容纳整个模式串。
for (int i = 0; i + pattern.length() <= text.length(); i++) {
int j = 0;
// 从模式串头部重新比较,失败后 i 只右移一位。
while (j < pattern.length() && text.charAt(i + j) == pattern.charAt(j)) {
j++;
}
if (j == pattern.length()) return i;
}
return -1;
}
static int[] lps(String p) {
// lps[i] 表示 p[0..i] 的最长相等真前缀/后缀长度。
int[] lps = new int[p.length()];
// len 表示当前位置之前可复用的最长相等前后缀长度。
for (int i = 1, len = 0; i < p.length(); ) {
if (p.charAt(i) == p.charAt(len)) {
// 当前字符接在已有公共前后缀后,长度增加 1。
lps[i] = len + 1;
i++;
len++;
} else if (len > 0) {
// 不移动 i,尝试当前公共前缀的次长可复用前后缀。
len = lps[len - 1];
} else {
// 已无更短候选,当前位置不存在公共真前后缀。
lps[i] = 0;
i++;
}
}
return lps;
}
static int kmp(String text, String p) {
Objects.requireNonNull(text);
Objects.requireNonNull(p);
if (p.isEmpty()) return 0;
int[] lps = lps(p);
for (int i = 0, j = 0; i < text.length(); ) {
if (text.charAt(i) == p.charAt(j)) {
// 匹配成功时两个指针一起前进。
i++;
j++;
if (j == p.length()) return i - j;
} else if (j > 0) {
// 文本 i 保持不动,模式串回退到最长可复用前缀之后。
j = lps[j - 1];
} else {
// 模式串首字符就失败,没有任何前缀可复用,只能移动文本指针。
i++;
}
}
return -1;
}
// 运行入口:对同一组文本和模式演示两种匹配算法。
public static void main(String[] args) {
String text = "ababcabcabababd",
p = "ababd";
System.out.println(bruteForce(text, p));
System.out.println(kmp(text, p));
}
}入口文本为 ababcabcabababd,模式为 ababd,两次打印的预期结果都是 10,这是按输入和代码推导的结果,不是实测输出。入口只演示一组普通输入,边界测试建议见第 8 节。
4.1 手工构造 LPS
模式串 ABABCABAB 的 LPS 可逐项推导为:
下标 i | 当前字符 | lps[i] | 最长相等真前后缀 |
|---|---|---|---|
| 0 | A | 0 | 无 |
| 1 | B | 0 | 无 |
| 2 | A | 1 | A |
| 3 | B | 2 | AB |
| 4 | C | 0 | 无 |
| 5 | A | 1 | A |
| 6 | B | 2 | AB |
| 7 | A | 3 | ABA |
| 8 | B | 4 | ABAB |
例如计算下标 4 的 C 时,先尝试长度 2 的 AB,但 C 与 pattern[2] 的 A 不等;回退到 lps[1] = 0 后,与首字符 A 仍不等,才确定该项为 0。最后一项为 4,因为 ABAB 同时是整个模式的前缀和后缀。
注意区分“当前比较下标”和“已匹配长度”:若在比较模式下标 8 时失配,此时 j = 8,应查 lps[7] = 3;若下标 8 也已匹配,则完整模式已经命中,本例直接返回。扩展为继续查找全部匹配的实现时,才会在报告命中后用 lps[8] = 4 保留重叠部分。
4.2 线性复杂度为什么成立
匹配阶段每轮要么让文本指针 i 增加,要么让模式指针 j 严格减小。i 最多增加 n 次,而 j 的累计回退次数不会超过它之前的累计增长次数,因此总操作数是线性的,不会退化成暴力算法的 O(nm)。
构建 LPS 也一样:i 只向前走,length 每次增长最多为 1,每次回退都严格减小且不会小于 0。累计回退次数受此前增长次数限制,所以虽然一个位置可能多次回退,整个构建过程仍是 O(m)。这是按状态变化推导的复杂度,不是性能测量。
4.3 流式匹配的实际价值
流式输入指数据分批到达,不必一次持有完整文本。处理日志流或网络分片时,历史文本可能无法回看。KMP 的匹配状态只需保留模式串、LPS 和当前 j,新分片到达后可以接着扫描;要返回全文中的位置,还需累计已消费的文本长度。
例如模式 abc,第一片为 xxab,处理结束时 j = 2;下一片开头是 c,就能完成跨片匹配。如果每片都把 j 清零,就会漏掉这次命中。第 4 节代码处理的是完整 String,并未实现流式接口;按字节接收数据时,还需处理解码状态,不能把独立解码每片与保持字符流连续性混为一谈。
5. 为什么 j 能回退而 i 不回退
假设已经匹配 j 个字符,接下来失配。若把模式起点向右移动,但仍保留一部分已读文本,那么保留的部分一定是旧匹配片段的后缀,又必须等于新一轮模式匹配的前缀。旧匹配片段等于 pattern[0..j-1],因此合法的保留长度正是这个模式片段的相等真前后缀长度。
lps[j - 1] 给出其中最长的长度,对应向右移动距离最小的候选起点。更长的保留长度不满足前后缀相等,已知不可能命中,可以直接排除;若该候选在当前文本字符处仍失配,再沿 LPS 继续尝试更短候选。
所以回退后保留的字符已经确认相等,不用重读;当前文本字符尚未匹配成功,i 也不能前进。开头例子中的 j 从 4 回退到 3,接着当前 a 匹配模式下标 3,再读到 b 即完成匹配。
6. 工程边界
Java String#indexOf 的内部实现可能随 JDK 和字符串编码变化,不能假设固定使用 KMP。完整字符串的一次性查找通常优先使用标准库;需要保留跨分片状态时,再评估专门的流式实现。
示例按 UTF-16 char 匹配并返回下标,这与 Java String 的索引单位一致。char 是一个 16 位编码单元;Unicode Code Point(码点)表示 Unicode 编码空间中的一个值,有些码点需要两个 char 表示;用户感知字符还可能由多个码点组成。因此 char 下标不等于用户看到的字符序号。若业务按码点或用户感知字符匹配,需要重新定义比较单位、索引与切分规则。
7. 单模式、多模式与正则的选择
- 单个固定模式、流式输入:KMP 能以
O(m)状态跨分片继续匹配; - 大量固定模式:逐个执行 KMP 会重复扫描文本,应评估 Trie(按前缀组织字符串的树)与 Aho-Corasick(用于多模式匹配的自动机)。前缀索引与全文多模式扫描的目标不同,不能直接互换;
- 需要字符类、重复和分组:属于正则表达式能力。字符类描述一组可匹配字符,重复描述出现次数,分组组织子表达式;某些引擎会回溯尝试不同路径,特定模式和输入可能放大成本,应按具体引擎评估;
- 模式很短或一次性调用:标准库通常更简单,内部实现也可能针对字符串编码优化。
选择算法前应先确认模式数量、是否需要流式状态、Unicode 语义,以及是否要求返回全部重叠匹配。
8. 验证与排障
以下是建议的检查方式:
- 暴力匹配作为小规模差分基线,即对同一输入比较暴力算法与 KMP 的结果;
- 覆盖空模式、空文本、模式长于文本、完全匹配、完全不匹配和重复前缀。对非空模式,文本为空或模式长于文本时应返回
-1; - 重叠命中和跨分片命中需针对相应扩展实现测试,不能用只返回首次命中的完整字符串示例证明。查找全部重叠命中时,报告一次命中后要保留
lps[m - 1]对应的状态,而不是直接清零; - 验证返回下标采用 UTF-16、Code Point 还是字节偏移;
- 流式实现需保存
j,并记录分片边界,不能在每个分片重新从 0 开始; - CPU 异常时区分模式构建、文本扫描、正则回溯和字符解码成本。
9. 容易踩的坑
- 真前缀不包含字符串自身。
- 失配时把
j直接归零,丢失复用信息。 - 构建 LPS 时忘记连续回退。
- 空模式串语义未定义,或在处理空模式前访问其首字符。
- 把
char下标当成码点或用户感知字符下标。 - 多模式场景逐个扫描全文,复杂度随模式数量线性放大。
10. 总结
KMP 通过复用模式串内部的前后缀关系,让文本扫描不必回退。
- LPS 描述模式前缀可复用的最长长度。
- 失配时移动模式指针,而不是重新扫描文本。
- 工程中优先标准库,但流式匹配和算法理解仍值得掌握。