字符串算法处理的是以字符序列为对象的匹配、比较与统计问题。它与其他数据结构算法的差别在于输入的基本单位是字符而非数值或指针:字符串的长度、字符集大小与编码方式直接进入复杂度公式,而“比较”本身也不再是一次指令,而是一次可能提前结束的内存扫描。字符串作为键的不可分解性与编码前提,其背景见 抽象数据类型(ADT) 与 数组与链表;复杂度记号的口径与“理论优于实测”的常见原因见 复杂度与算法分析;字符与码点、变长编码对“第 i 个字符”这一假设的干扰见 Java 时间处理与字符编码,字符串在内存与字节流之间的表示差异见 序列化与反序列化。
一、起源:文本检索与模式匹配的普遍需求
1.1 从“包含”判断说起
文本处理中最常见的一类问题是判断一个较短的串(模式,pattern)是否出现在一个较长的串(文本,text)中,以及出现在哪些位置:
| 场景 | 文本 | 模式 | 关注点 |
|---|---|---|---|
| 编辑器查找 | 文件内容 | 用户输入的关键词 | 全部出现位置、高亮 |
| 日志检索 | 日志行或整个日志文件 | 错误码、请求标识、堆栈片段 | 命中行、上下文 |
| 敏感词过滤 | 用户提交的文本 | 词库中的大量词条 | 是否命中、替换边界 |
| 生物序列比对 | 基因序列 | 待查片段、参考序列 | 近似匹配、允许错配 |
| 输入校验 | 表单字段 | 格式规则(邮箱、手机号) | 是否整体匹配 |
这些场景的差异很大:有的只需要“是否存在”,有的需要全部位置;模式可能是一个,也可能是几万条;文本可能是几 KB 的输入框内容,也可能是几十 GB 的日志。把它们抽象出来,得到的是同一族问题:在字符序列上描述并识别某种结构。
1.2 暴力匹配与重复比较
最直接的解法是把模式在文本上滑动,逐个对齐位置尝试匹配:
naiveSearch(text, pattern):
n = len(text), m = len(pattern)
for i in 0 .. n - m:
j = 0
while j < m and text[i + j] == pattern[j]:
j++
if j == m:
记录位置 i
这个过程的代价表面上与文本长度成正比,但内层比较的次数不只取决于外层的对齐次数。看一组退化输入:
text = a a a a a a a a a b
pattern = a a a a b
对齐 i = 0: a a a a a ... 前 4 个字符匹配,第 5 个失配(text[4]=a, pattern[4]=b)
对齐 i = 1: a a a a b ... 前 4 个字符匹配,第 5 个失配
对齐 i = 2: ... 前 4 个字符匹配,第 5 个失配
...
每个对齐位置都比较了 m 个字符才失败,共约 n 个对齐位置,总比较次数 ≈ n × m
问题的根源在于每一次失配之后,已经获得的匹配信息被全部丢弃。在第 i 个对齐位置,内层循环已经确认了 text[i..i+3] 与 pattern[0..3] 相等,也就是已经知道 text[i..i+3] 全是 a;但当外层把 i 加一以后,这份信息没有被利用,程序又从 pattern[0] 开始重新比较。
- 对于随机文本与随机模式,首个字符即失配的概率很高,平均比较次数接近常数,暴力匹配表现良好;
- 对于周期性强、重复字符多的输入(同一字符的连续段、
abababab这类周期串、碱基序列),失配发生在模式的靠后位置,比较次数接近上界。
复杂度因此需要分成两个口径写出:
最好:O(n) 每个对齐位置首次比较即失配
平均:接近 O(n) 随机输入下
最坏:O(n × m) 文本与模式都由重复字符构成,如 text = a^n,pattern = a^(m-1)b
“最坏情况能否被触发”不是理论游戏:日志里的长串分隔符、DNA 序列、二进制转十六进制后的文本都可能出现长重复段,而模式串一旦较长,n × m 就足以让单次请求超时。
1.3 预处理换运行时间
暴力匹配的浪费在于“同一个文本片段被反复比较”。要消除这种浪费,方向只有一个:在匹配开始之前,对模式(或文本)做一次预处理,把“失配后应该从哪里继续”这一信息预先算出来,使得匹配阶段不必回退、不必重复比较。
这条思路产生了本章的四种算法,它们的区别在于“预处理的对象”与“利用的结构”不同:
| 算法 | 预处理对象 | 记录的信息 | 匹配阶段的行为 |
|---|---|---|---|
| KMP | 模式 | 每个位置的最长相等真前缀与真后缀 | 文本指针不回退,只移动模式侧的指针 |
| Rabin-Karp | 模式(或文本窗口) | 子串的哈希值 | 用哈希比较代替逐字符比较,命中后再校验 |
| Z 函数 / 扩展 KMP | 模式与文本的拼接串 | 每个后缀与整个串的最长公共前缀 | 一次线性扫描得到所有位置的匹配长度 |
| AC 自动机 | 整个模式集合 | 字典树与失配指针 | 文本扫描一遍,同时匹配全部模式 |
这四种算法的共同前提是:预处理的开销 O(m) 或 O(模式总长) 可以被后续的匹配摊薄。因此当文本很长、或模式需要在同一份文本上反复检索时,预处理的收益最大;若只做一次短文本上的包含判断,暴力匹配或语言内置的查找函数反而是合适的(内置实现通常已经做了常数优化,如 Boyer-Moore 式的跳跃)。
二、原理
1. 问题分类
在进入具体算法之前,先按四个维度区分问题,因为不同维度的最优解并不相同。
维度一:单模式与多模式。
单模式:一个模式串,一遍文本扫描
多模式:一个模式集合,需要找出所有模式的出现
逐个跑单模式算法的代价是 O(k × n)(k 为模式数),此处需要专门的多模式算法
维度二:精确匹配与近似匹配。
精确匹配:要求逐字符完全相等
近似匹配:允许若干次插入、删除、替换(编辑距离),或允许通配符
近似匹配的代价显著更高,通常需要动态规划或带剪枝的自动机,见第三节第 6.4 小节
维度三:查询的形态。 字符序列上的查询不止“子串是否存在”一种:
| 查询 | 形式 | 典型结构 |
|---|---|---|
| 前缀查询 | 集合中以某串开头的元素 | 字典树,见 字典树与字符串索引 |
| 子串查询 | 文本中是否包含某串 | KMP、Rabin-Karp、Z 函数 |
| 最长公共前后缀 | 一个串的最长相等真前缀与真后缀 | KMP 的前缀函数 |
| 回文 | 正读反读相同的子串 | Manacher |
| 最长公共子串 | 两个串共有的最长子串 | 后缀自动机、后缀数组、动态规划 |
| 字典序比较与排序 | 按字符编码逐位比较 | 后缀数组、比较器 |
维度四:在线与离线。 在线算法按文本从前往后的顺序处理,文本无需一次全部读入,适合流式场景;离线算法可以访问整个文本,允许构建全局结构(如后缀数组)。KMP 是典型的在线算法——它不需要回看已经读过的文本;后缀数组是典型的离线结构。这一区别在“文本是日志流、无法重复读取”的场景中直接决定可行性。
2. 暴力匹配与其失效分析
第 1.2 小节给出了最坏情况的构造。这里把“比较次数的浪费来源”精确化为两条。
浪费一:错位的对齐位置仍然从模式首部开始比较。
对齐 i 失败后,程序从 i + 1 重新开始。
但在对齐 i 的匹配过程中,已经确认了 text[i..i+j-1] == pattern[0..j-1]。
前一个对齐位置的后缀信息,恰好是新对齐位置的前缀信息。
浪费二:模式自身的周期性没有被打包成结构。
若模式的前缀与后缀存在重复(如 abab 的前 2 个字符与后 2 个字符相等),那么在某次失配后,模式可以整体“右移”一段距离而无需重新比较这段公共部分。暴力匹配没有记录“模式自己与自己有多少公共前后缀”,因此每次都要重新发现这一点。
这两条浪费都指向同一个改进方向:把“模式的前缀与后缀的相等关系”预先算出来。这正是 KMP 前缀函数的内容。
3. KMP
3.1 前缀函数(部分匹配表)的定义
KMP 的核心是模式的前缀函数(failure function / partial match table)。对模式串 p 的每个前缀 p[0..i],定义:
pi[i] = 最大的 k(k < i + 1),使得
p[0..k-1] == p[i-k+1..i]
即:p[0..i] 的“既是真前缀、又是真后缀”的最长字符串的长度。
“真”指长度小于 i + 1,即不允许取整个前缀本身。
以 p = "ababaca" 为例:
下标 i : 0 1 2 3 4 5 6
字符 : a b a b a c a
pi[i] : 0 0 1 2 3 0 1
说明:
i = 2("aba") 真前缀 "a" 与真后缀 "a" 相等,长度 1
i = 3("abab") 真前缀 "ab" 与真后缀 "ab" 相等,长度 2
i = 4("ababa")真前缀 "aba" 与真后缀 "aba" 相等,长度 3
i = 6("ababaca")真前缀 "a" 与真后缀 "a" 相等,长度 1
前缀函数承载的信息是模式在某个位置失配时,已经匹配的那一段前缀能提供多少“仍然有效”的匹配。若在模式的第 j 位失配(即 pattern[0..j-1] 已匹配),则已经匹配的这一段 text[i-j..i-1] 等于 pattern[0..j-1];它的最长相等真前缀长度为 pi[j-1],因此可以把模式右移 j - pi[j-1] 位,直接从 pattern[pi[j-1]] 继续比较。这段被保留下来的前缀与刚才匹配的文本后缀相等,无需重新比较。
失配跳转的依据:
pattern[0..j-1] 已经与文本匹配,且 pattern[0..pi[j-1]-1] == pattern[j-pi[j-1]..j-1]
⇒ text[i-pi[j-1]..i-1] == pattern[0..pi[j-1]-1]
⇒ 模式可以直接平移,让 pattern[pi[j-1]] 与 text[i] 对齐继续比较
3.2 递推求法
前缀函数可以由前一位的结果递推,不必对每个位置单独求最长公共前后缀:
for i in 1 .. m-1:
j = pi[i-1] // 先从“前一位的最长长度”出发
while j > 0 and p[i] != p[j]:
j = pi[j-1] // 失配就退到更短的一个候选长度
if p[i] == p[j]:
j++ // 可以再延长一位
pi[i] = j
递推的正确性来自一条性质:pi[i] 的候选值必然落在 pi[i-1] 的候选链上。也就是说,p[0..i] 的所有公共前后缀长度构成一条链,链上的下一个值是 pi 在更短长度上的取值,因此从 pi[i-1] 出发沿 pi 反复回退,就能覆盖全部候选,无需枚举。
以 ababaca 的后半段为例:
i = 5(字符 c):
j 从 pi[4] = 3 出发,p[5] = 'c' ≠ p[3] = 'b',回退 j = pi[2] = 1
p[5] = 'c' ≠ p[1] = 'b',回退 j = pi[0] = 0
p[5] = 'c' ≠ p[0] = 'a',j 保持 0
pi[5] = 0
3.3 复杂度分析:指针不回退
前缀函数的计算与匹配过程都是线性的,关键证据是回退的深度总量有界:
前缀函数计算:
j 每次至多加 1(循环中 i 每前进一步,j 至多增加 1),共增加不超过 m
j 只能通过回退减小,而 j 始终非负,因此回退的总次数不超过 m
⇒ 总比较次数 O(m)
匹配过程:
文本指针 i 只增不减(不回退)
模式侧指针 j 的增量总和不超过文本长度 n,回退总量同样有界
⇒ 总比较次数 O(n + m)
这条论证的形式与 AC 自动机中 fail 链上溯的均摊分析相同(见第 7 小节):一个单调递增的量(已匹配长度)配上“增量有界、只能通过回退减少、且非负”这三个条件,就足以把看似嵌套的循环化为线性。复杂度分析的一般手法见 复杂度与算法分析 的摊还分析一节。
3.4 next 数组的不同约定
教材与代码中“next 数组”有多种约定,互相换算时容易出错,需要在使用前确认:
| 约定 | 定义 | 失配时的动作 | 备注 |
|---|---|---|---|
本文的 pi | pi[i] 为 p[0..i] 的最长公共前后缀长度 | j = pi[j-1] | 最常见,取值与“已匹配长度”同量纲 |
右移一位的 next | next[i] = pi[i-1](next[0] = -1) | j = next[j] | 早期教材的写法,便于统一“j 为 -1 特判” |
加一约定的 next | next[i] = pi[i] + 1 | 需要与下标语义一并看 | 部分教材采用,直接比较会错位 |
三种约定的本质完全相同,差异只是“数组下标与模式下标的对齐方式”。混用不同约定的代码是最常见的 KMP 出错原因之一,处理方式是:选定一种约定后,在注释中写明“pi[i] 表示 p[0..i] 的最长公共前后缀长度”,并只用这一个口径。
4. Rabin-Karp
4.1 滚动哈希的思想
Rabin-Karp 换一个角度:不比较字符,而比较哈希值。把每个长度为 m 的文本窗口当作一个数,用多项式滚动哈希计算它的值:
H(s[0..m-1]) = (s[0] × base^(m-1) + s[1] × base^(m-2) + ... + s[m-1]) mod mod
关键性质是相邻窗口之间的增量关系:窗口右移一位,等价于“去掉最高位、整体乘 base、加上新字符”:
H(s[i+1..i+m]) = (H(s[i..i+m-1]) − s[i] × base^(m-1)) × base + s[i+m] (在模 mod 下)
因此窗口滑动一次只需要常数次运算,不必对窗口内 m 个字符重新求和。整个文本扫描一遍即可算出全部窗口的哈希值,与模式的哈希值比较。
预处理:O(m)
匹配: 每个窗口 O(1) 的增量更新,共 O(n) 次,每次与模式哈希比较
哈希函数的构造、模数与进制的选择、溢出处理,与散列表中字符串散列是同一套内容,见 散列表 的字符串散列一节。
4.2 哈希冲突的处理
只比较哈希值会引入假阳性:两个不同的字符串可能得到相同的哈希值(冲突)。因此 Rabin-Karp 的完整流程是“哈希相等后再逐字符校验”:
for i in 0 .. n-m:
if H(text[i..i+m-1]) == H(pattern):
if text[i..i+m-1] == pattern: // 真正校验,排除假阳性
记录位置 i
三种处理冲突的方式:
| 方式 | 做法 | 取舍 |
|---|---|---|
| 单哈希 + 校验 | 哈希相等时逐字符比较 | 实现简单;理论上最坏可被构造为哈希全部相等,退化为 O(nm) |
| 双哈希 | 用两组 (base, mod) 同时计算,两者都相等才比较 | 冲突概率大幅下降;代价是常数翻倍,模运算次数加倍 |
| 随机模数 | 运行时随机选取 base 与 mod | 使攻击者无法离线构造冲突串;代价是结果不可复现 |
冲突概率的量级可以估算:若模数取 2³¹ 量级且均匀分布,单次比较的假阳性概率约为 1/mod。但模数过小时风险显著,且若字符集与进制选择不当(例如 base 与 mod 不互质、或字符值包含 0 导致前导字符信息丢失),可能被刻意构造出大量同哈希串。工程上更稳妥的做法是双哈希,或使用 64 位无符号溢出(取 mod = 2⁶⁴)配合随机 base。
4.3 复杂度与适用场景
预处理:O(m)
期望匹配:O(n + m) 哈希均匀、冲突少
最坏匹配:O(n × m) 全部窗口的哈希都与模式相等,每次都要逐字符校验
空间: O(1)(单哈希)或 O(n)(预计算幂数组以便随机访问子串哈希)
Rabin-Karp 的价值不在单模式匹配(此场景下 KMP 有确定的最坏保证),而在两类场景:
- 多模式匹配。把模式集合按长度分组,对同一长度的模式用同一套哈希计算,再去集合中查表;这样一次文本扫描可以同时检查多个等长模式。代价是不同长度需要分别扫描。
- 二维匹配。在矩阵中寻找子矩阵,可以把每行先做一次一维滚动哈希,得到一个“行哈希数组”,再对这个数组做列方向的一维哈希,从而把二维问题化为两次一维滚动哈希。
- 子串的快速比较与去重。预计算前缀哈希与幂数组后,任意两个子串是否相等可以在 O(1) 内比较,这是字符串去重、最长重复子串、回文判定等问题的常用手段(见第 8 小节与第三节第 2 小节)。
5. Z 函数与扩展 KMP
5.1 Z 数组的定义
Z 函数(也称扩展 KMP 的核心数组)定义在单个串上:对串 s 的每个位置 i,z[i] 表示从 i 开始的后缀与整个串 s 的最长公共前缀的长度:
z[i] = LCP(s, s[i..]),即最大的 k 使得 s[0..k-1] == s[i..i+k-1]
约定 z[0] = 0(或按实现取 len(s),需在注释中写明)
以 s = "aabcaabxaa" 为例:
下标 : 0 1 2 3 4 5 6 7 8 9
字符 : a a b c a a b x a a
z[i] : - 1 0 0 3 1 0 0 2 1
说明:
i = 1:s[1..] = "abcaabxaa",与 s 的公共前缀为 "a",长度 1
i = 4:s[4..] = "aabxaa",与 s 的公共前缀为 "aab",长度 3
i = 8:s[8..] = "aa",与 s 的公共前缀为 "aa",长度 2
5.2 线性求法:区间复用
Z 函数的线性求法与 Manacher 的思路同源:维护当前已知的最右匹配区间,落在区间内的位置可以复用对称位置的结果。
维护一个区间 [l, r],表示目前发现的“最靠右”的匹配(s[l..r] == s[0..r-l])
求 z[i]:
if i <= r:
z[i] = min(r - i + 1, z[i - l]) // 复用对称位置的结果,受右边界约束
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i]++ // 边界内继续比较
if i + z[i] - 1 > r: // 更新最右区间
l = i; r = i + z[i] - 1
与 KMP 的前缀函数相比,两者的信息结构不同:pi[i] 描述的是“前缀 p[0..i] 内部的前后缀重合”,而 z[i] 描述的是“后缀 s[i..] 与整个串 s 的重合”。两者的线性证明都依赖“已匹配区间单调右移、比较总量有界”。
5.3 与 KMP 的关系与适用差异
| 维度 | KMP 前缀函数 | Z 函数 |
|---|---|---|
| 定义对象 | 前缀 p[0..i] 的最长公共前后缀 | 后缀 s[i..] 与 s 的最长公共前缀 |
| 匹配时的用法 | 利用失配跳转,文本指针不回退 | 拼接 pattern + 分隔符 + text 后,z 值等于 m 的位置即匹配位置 |
| 分隔符的作用 | 不需要 | 必须用文本与模式中都不出现的字符分隔,防止匹配跨越边界 |
| 适用问题 | 单模式匹配、字符串周期 | 单模式匹配、两个串的任意后缀 LCP、字符串压缩表示 |
用 Z 函数做单模式匹配的写法是把模式与文本用分隔符拼起来,再对整个串求 Z:
s = pattern + '#' + text // '#' 不出现在 pattern 与 text 中
z[i] == len(pattern) ⇒ 位置 (i - len(pattern) - 1) 处出现一次匹配
两种方法在单模式匹配上复杂度相同(O(n + m))。选择依据是问题形态:需要反复求“某个后缀与某个前缀的 LCP”时,Z 函数的语义更直接;需要流式处理或需要前缀函数承载周期信息时,KMP 更合适。
5.4 周期与最小循环节
前缀函数直接给出了字符串的周期结构。若长度为 n 的串 s 满足 pi[n-1] = k,则 s 有一个长度为 n - k 的循环节;当 n - k 整除 n 时,s 由该循环节恰好重复 n / (n - k) 次构成。
最小循环节长度 = n − pi[n-1]
n % (n − pi[n-1]) == 0 ⇒ s 由该循环节整数次重复而成
n % (n − pi[n-1]) != 0 ⇒ 该长度是周期但不整除,需补齐才能构成完整循环节
例:s = "ababab"
pi[5] = 4,n − pi[5] = 2,n % 2 == 0
⇒ 最小循环节为 "ab",重复 3 次
这条结论在字符串压缩、循环移位判定(判断 b 是否为 a 的循环移位串,即判断 b 是否为 a + a 的子串)、以及“由字符串重复若干次构成”的题目中是标准手段。
6. 回文与 Manacher
6.1 中心扩展的复杂度问题
回文子串的中心可能是单个字符(奇数长度,如 aba),也可能是两个字符之间(偶数长度,如 abba)。以每个中心向外扩展的朴素做法:
对每个中心 c:
向两侧扩展,直到字符不相等或越界
记录的扩展长度即为以 c 为中心的最长回文半径
中心个数 O(n),每个中心最多扩展 O(n)
⇒ 最坏 O(n²)
最坏情况出现在高度回文的输入上,如 aaaa...a:每个中心都能扩展到边界,总代价为 O(n²)。与暴力匹配类似,这里的浪费是相邻中心之间存在大量重复比较——若一个很长的回文已经把某个区间覆盖,那么该区间内的中心其对称位置的结果可以被复用。
6.2 半径数组与对称复用
Manacher 的做法是维护“当前已经扩展到的最右回文边界”及其中心,利用回文自身的对称性跳过重复比较:
设 c 为当前最右回文的中心,r 为其右边界(i < r 时说明 i 落在某个已知回文内部)
对当前位置 i,其关于 c 的对称点为 mirror = 2c − i
p[mirror] 已经完全落在 [c 的回文] 内部 → p[i] 至少等于 p[mirror]
否则 p[i] 至少等于 r − i(受右边界截断)
在此基础上继续向两侧扩展,并更新 c 与 r
复杂度为 O(n),理由与 Z 函数相同:r 只增不减,扩展的总步数与 n 同阶。
6.3 统一奇偶长度
奇数长度与偶数长度的回文中心不同,会造成两套边界判断。Manacher 的标准处理是在字符之间插入分隔符,把所有回文都变成奇数长度:
原串: a b b a
扩展: # a # b # b # a # (长度为 2n + 1)
偶数长度回文 "bb" 在扩展串中以某个 '#' 为中心
奇数长度回文 "aba" 在扩展串中以字符 'a' 为中心
扩展串上的半径 p[i] 与原串的对应关系是:
最长回文子串长度 = max(p)
原串起始下标 = (中心下标 − 半径) / 2
6.4 最长回文子串与回文划分
- 最长回文子串:取半径数组的最大值,按上式映射回原串下标即可。
- 回文子串计数:每个中心贡献的半径即为该中心下不同长度的回文个数之和。
- 回文划分(把字符串切成若干段,每段都是回文,求最少段数):需要判定“任意子串是否为回文”。Manacher 给出的半径数组可以 O(1) 回答任意中心的最长回文,但任意区间的回文判定仍需配合动态规划或哈希预处理;用滚动哈希判定任意子串是否回文(比较正序与反序哈希)是常见替代方案。
7. 多模式匹配:字典树与失配指针
7.1 从单模式到多模式
若模式集合有 k 个模式,逐个跑 KMP 的代价是 O(k × n)。多模式匹配的改进方向是用模式集合构建一棵字典树,然后让文本在这棵树上走一遍:文本从根出发,沿字符逐层下降,走到某个节点就说明其对应的前缀出现。字典树的结构、节点语义与终标记的定义见 字典树与字符串索引。
朴素做法的问题在于失败处理:若文本在某个节点处找不到对应字符的分支,就要回到根重新开始,此前匹配到的后缀信息被丢弃。
7.2 失配指针与 AC 自动机
AC 自动机(Aho-Corasick automaton)在字典树的每个节点上增加一个失配指针(fail 指针),把失败后的回退从“回到根”改为“退到当前前缀的最长真后缀,且该后缀仍是某模式的前缀”的位置:
fail(u) 的定义:
对节点 u(代表前缀 P),fail(u) 指向节点 v,使得
v 代表的前缀是 P 的最长真后缀,且 v 代表的前缀是某个模式串的前缀
这与 KMP 的前缀函数在语义上完全一致:KMP 的失配跳转是“模式内部的最长公共前后缀”,AC 的 fail 是“字典树节点沿祖先方向的最长可用后缀”,前缀从一维线性结构推广为树上的路径,失配回退也就从链回退推广为 fail 链上溯。两者的对照在 字典树与字符串索引 的有限状态自动机一节有完整讨论。
7.3 构造与转移
fail 指针通过**广度优先搜索(BFS)**逐层构建,因为一个节点的 fail 指向的必然是深度更小的节点。广度优先遍历的一般形态见 图的表示与遍历。
1. 根节点的 fail 指向自身(或视为空),根的第一层孩子的 fail 指向根
2. 按 BFS 顺序处理节点 u,对其字符 c 分支 v:
设 f = fail(u)
若 f 有字符 c 分支,则 fail(v) = f.children[c]
否则沿 fail 链继续上溯,直到找到有 c 分支的节点或到达根
3. 若 v 本身是某个模式的终点,或 fail(v) 是,则 v 也是输出节点
第 3 条即“输出沿 fail 链继承”。若模式集合中存在一个是另一个后缀的模式(如 he、she),则匹配到 she 时的节点必须同时报告 he,否则会漏掉被更长模式覆盖的短模式。
转移继承(trie 图优化) 把匹配阶段的 fail 链上溯提前到构造阶段:对每个节点的每个字符,若该字符没有对应分支,就把这个位置的转移直接指向 fail 节点对应字符的转移。这样匹配时每一步都是一次数组访问,无需 while 循环上溯,代价是转移表的大小成为 O(节点数 × 字符集大小)。
7.4 复杂度与输出方式
构造(不含转移继承):O(Σ|p_i|),BFS 加上均摊 O(1) 的 fail 链上溯
构造(含转移继承): O(|Σ| × Σ|p_i|),换来匹配时无上溯
匹配: O(n + 匹配出现数),n 为文本长度
空间: O(Σ|p_i|),每节点一个 fail 指针;含转移表时再乘字符集大小
输出与计数的三种方式:
| 方式 | 做法 | 说明 |
|---|---|---|
| 沿 fail 链上报 | 匹配到节点后沿 fail 链逐级检查输出标记 | 空间省,但每步可能上溯,输出多时变慢 |
| 构造时合并输出 | 构建时把 fail 祖先的输出并入本节点 | 匹配时 O(1) 取输出;复用输出集合,需注意内存 |
| 差分计数 | 先累加每个节点的到达次数,再沿 fail 树自底向上累加 | 统计全部模式出现次数时最省,避免逐个上报 |
“统计出现次数”与“报告出现位置”是两个不同量级的问题:前者可以用差分计数在 O(Σ|p_i| + n) 内完成,后者必须按实际出现数输出,代价中包含结果规模。
8. 字符串比较与排序
8.1 字典序与比较规则
字符串的自然次序是字典序:从左到右逐位比较字符编码,第一个不相等的位置决定大小;若一个串是另一个的前缀,则较短的更小。
"app" < "apple" 前者是后者的前缀
"apple" < "apply" 第 5 位 'e' < 'y'
两点工程影响:
- 比较的代价与公共前缀长度成正比。两个长串若共享长前缀,比较需要扫描很长一段才分出大小,这与整数比较的一次指令形成对比。
- 次序由编码决定,而非由“字母表直觉”决定。ASCII 中大写字母排在小写字母之前(
'Z' < 'a');Unicode 中不同语言的字符次序与码点次序并不一致,面向用户的排序需要排序规则(collation) 而非简单按码点比较。字符与码点的关系、UTF-8 与 UTF-16 的差异见 Java 时间处理与字符编码。
8.2 后缀数组与后缀自动机的定位
在单个长文本上反复查询“任意子串是否出现”“最长重复子串”等问题时,索引对象是该文本的全部后缀:
| 结构 | 组织方式 | 支持的操作 | 构造代价 |
|---|---|---|---|
| 后缀树 | 全部后缀构成的压缩字典树 | O(m) 子串查询、最长重复子串、最长公共子串 | 构造复杂,节点与边开销大 |
| 后缀数组 | 全部后缀按字典序排序后的起始位置,配合 LCP 数组 | 子串查询、最长重复子串(借助 LCP) | 可实现 O(n) 或 O(n log n) |
| 后缀自动机 | 全部子串构成的最小确定性自动机 | 子串出现次数、最长重复子串、不同子串计数 | O(n) |
三者的共同点是“把文本的全部子串或后缀组织成结构,使子串查询脱离“逐个位置比较”的方式”。它们与字典树解决的不是同一个问题:字典树索引的是一个字符串集合的前缀,后缀结构索引的是一个文本内部的全部子串。当只需要子串存在性判断时,工程中通常直接使用全文索引组件或对文本构建滚动哈希索引。
8.3 字符串哈希在去重与比较中的用途
滚动哈希(第 4 小节)提供了一种 O(1) 比较任意两个子串是否相等的手段,代价是存在可忽略的假阳性概率(配合双哈希或额外校验)。它的两类用途:
- 去重与指纹:把长字符串(文件内容、日志行、请求体)映射为定长哈希值,用哈希值集合判断是否出现过,或作为缓存键、内容指纹。此时哈希值只承担“相等判定”的角色,与散列表的键契约同源,见 散列表;当元素数量极大、只能接受近似判断时,可以进一步退化为位数组上的多重散列,见 位图与布隆过滤器。
- 子串比较加速:最长重复子串、最长公共子串、回文判定、字符串比较类问题中,把 O(m) 的逐字符比较替换为 O(1) 的哈希比较,再配合二分查找长度,可把整体代价从 O(nm) 降到 O(n log n)。
需要强调的是:哈希比较是概率正确的,相等需要逐字符确认,不等则一定正确。在结果必须严格正确的场合,哈希只作为过滤手段,最终仍需精确校验。
三、实现
1. KMP 实现要点
1.1 前缀函数的计算
// 前缀函数:pi[i] = p[0..i] 的最长相等真前缀与真后缀的长度
static int[] prefixFunction(String p) {
int m = p.length();
int[] pi = new int[m];
for (int i = 1; i < m; i++) {
int j = pi[i - 1]; // 先取前一位的结果作为候选长度
while (j > 0 && p.charAt(i) != p.charAt(j)) {
j = pi[j - 1]; // 失配则沿前缀链回退,注意是 j-1 而非 j
}
if (p.charAt(i) == p.charAt(j)) {
j++; // 可以再延长一位
}
pi[i] = j;
}
return pi;
}
三处下标细节决定了实现的正确性:
- 回退时用
pi[j - 1]。j表示“待比较的下一位下标”,而pi数组以“已匹配长度”为语义,二者相差一位。写成pi[j]会造成越界或错误跳转。 while与if的顺序。必须先回退到“能延长”的位置,再判断是否相等并加一;若先加一,会把一个不匹配的延长计入结果。i从 1 开始,pi[0] = 0。单个字符不存在真前缀,取 0 是唯一定义。
1.2 匹配循环与全部匹配位置
// 在 text 中查找 pattern 的全部出现位置(返回起始下标)
static List<Integer> kmpSearch(String text, String pattern) {
List<Integer> res = new ArrayList<>();
if (pattern.isEmpty()) {
for (int i = 0; i <= text.length(); i++) {
res.add(i); // 空模式在任意位置都匹配,需要显式定义语义
}
return res;
}
int[] pi = prefixFunction(pattern);
int m = pattern.length();
int j = 0; // j 为“已匹配的模式前缀长度”
for (int i = 0; i < text.length(); i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1]; // 失配:跳转到最长可用的真前缀
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == m) { // 完全匹配
res.add(i - m + 1); // 起始下标 = 当前下标 - 模式长度 + 1
j = pi[j - 1]; // 继续查找重叠出现,不可置 0
}
}
return res;
}
关键点有三条:
- 文本指针
i在循环中不回退,这是 O(n) 的来源;模式的平移通过j的变化实现。 - 匹配成功后把
j置为pi[j - 1]而不是 0,才能找到重叠的出现(如文本aaaa中模式aa在位置 0、1、2 各出现一次)。若只需要不重叠的匹配,则置 0 并跳过 m 个字符。 - 空模式必须显式定义语义。此处约定“在任意位置都匹配”,若业务不需要,应直接返回空列表,避免调用方误用。
1.3 常见下标错误与调试方法
| 错误写法 | 症状 | 原因 |
|---|---|---|
回退写 j = pi[j] | 数组越界或跳转错误 | pi 与 j 差一位 |
匹配成功后 j = 0 | 漏掉重叠出现 | 未利用已匹配前缀的后缀信息 |
pi[i] 用 j = pi[i-1] 后不重新判断相等 | 结果偏小或偏大 | 漏掉 if (p[i] == p[j]) j++ 这一步 |
| 混用两套 next 约定 | 结果整体错位 | 下标语义不一致 |
调试方法是用短串手工推演,并与暴力匹配的结果逐位对照:
对照用例(覆盖典型边界):
text = "aaaaa", pattern = "aa" → 位置 0,1,2,3(重叠)
text = "abababa", pattern = "aba" → 位置 0,2,4(重叠)
text = "abc", pattern = "abcd" → 无匹配(模式长于文本)
text = "abc", pattern = "" → 需按约定处理
text = "aab", pattern = "ab" → 位置 1
text = "aaa", pattern = "aaa" → 位置 0(完全重合)
2. 滚动哈希实现要点
2.1 模数与进制的选择
public final class RollingHash {
private final long mod;
private final long base;
private final long[] pow; // pow[i] = base^i mod mod
private final long[] pre; // pre[i] = s[0..i-1] 的哈希
public RollingHash(String s, long base, long mod) {
this.base = base;
this.mod = mod;
int n = s.length();
pow = new long[n + 1];
pre = new long[n + 1];
pow[0] = 1;
for (int i = 0; i < n; i++) {
pow[i + 1] = pow[i] * base % mod;
pre[i + 1] = (pre[i] * base + s.charAt(i)) % mod;
}
}
// 子串 s[l..r) 的哈希,O(1)
public long hash(int l, int r) {
long h = (pre[r] - pre[l] * pow[r - l]) % mod;
return h < 0 ? h + mod : h; // 处理取模后的负数
}
}
两处选择需要说明:
- 进制
base应大于字符集的最大字符值,且与模数互质。常见取 131、1313、131313 等质数。若base取小写字母数量 26 且字符值直接用'a'起算,会出现不同字符串哈希相同的构造(如"a" + 某字符与另一个字符的组合)。工程上直接用字符的码点(charAt(i))而非其在字符集中的下标可以避免这类混叠。 - 模数取大质数(如 10⁹+7、10⁹+9)。模数过小会显著抬高冲突概率;取 2⁶⁴ 的溢出(即不显式取模,依赖
long的自然溢出)性能更好,但需要接受约 2⁻³² 量级的碰撞概率(生日攻击下更易被构造)。
2.2 溢出与负数处理
pre[l] * pow[r - l] 可能溢出 long 的范围。两条路线:
路线一:显式取模。全部中间结果落在 [0, mod) 内,乘法不会溢出(mod < 2^31 时安全)
路线二:自然溢出。不取模,依赖 long 的模 2^64 语义;单次乘法溢出不报错,但结果不可读
减法 pre[r] - pre[l] * pow[r - l] 在取模意义下可能为负,必须补模后再返回,否则同一子串在不同调用中可能取到两种值(负数与补模后的正数),导致比较失败。
2.3 双哈希与拒绝采样
// 双哈希:两组不同的 (base, mod),两者都相等才认为子串相等
boolean same(int l1, int r1, int l2, int r2) {
return h1.hash(l1, r1) == h1.hash(l2, r2)
&& h2.hash(l1, r1) == h2.hash(l2, r2);
}
两种控制冲突的策略:
| 策略 | 做法 | 适用 |
|---|---|---|
| 双哈希 | 并发两组模数,全等才判定相等 | 通用;冲突概率约为两组概率之积 |
| 随机化 | 运行时随机取 base(与模数互质) | 防御“针对固定哈希的构造攻击”;结果不可复现 |
| 拒绝采样 | 若某次比较只有哈希相等而内容不等,记录并更换参数重新计算 | 极少使用;实现成本高 |
用哈希去重时不能只依赖哈希值相等:大规模去重(日志行、文件指纹)中,应保留原始内容或额外做一次逐字节校验;若只做哈希比较,冲突会表现为“两条不同数据被判定为同一条”,这类缺陷在数据量大时才会暴露,排查困难(见第 7 小节)。
3. Manacher 实现要点
3.1 插入分隔符统一奇偶
// 返回扩展串上每个位置的回文半径 p[i](含中心字符本身)
static int[] manacherRadii(String s) {
StringBuilder sb = new StringBuilder("#");
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i)).append('#');
}
String t = sb.toString(); // 长度为 2n + 1,奇偶长度统一
int n = t.length();
int[] p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = 1; // 至少包含中心字符自身
}
int c = 0, r = 0; // c 为当前最右回文中心,r 为其右边界
for (int i = 0; i < n; i++) {
if (i < r) {
int mirror = 2 * c - i; // i 关于 c 的对称点
p[i] = Math.min(r - i, p[mirror]); // 对称复用,但不得超过右边界
}
while (i - p[i] >= 0 && i + p[i] < n
&& t.charAt(i - p[i]) == t.charAt(i + p[i])) {
p[i]++; // 边界内继续扩展
}
if (i + p[i] > r) { // 更新最右回文,r 单调不减
c = i;
r = i + p[i];
}
}
return p;
}
分隔符必须不在原串中出现。若原串可能包含任意字符(如二进制数据、用户输入),应使用一个不会与输入冲突的编码方式(例如先做转义,或在算法中以“间隙”而非实际字符表示),避免分隔符与真实字符相等导致回文边界错误。
3.2 边界维护与结果映射
r的语义是“右开区间”还是“右闭区间”必须统一。上面的实现中p[i]是半径长度(包含中心),r = i + p[i]表示下一个待考察的位置,因此对称复用取min(r - i, p[mirror])。若改用闭区间写法(r = i + p[i] - 1),min的表达式要相应改为min(r - i + 1, p[mirror])。两种写法都对,混用则出错。- 结果映射回原串:
static String longestPalindrome(String s) {
int[] p = manacherRadii(s);
int bestCenter = 0;
for (int i = 0; i < p.length; i++) {
if (p[i] > p[bestCenter]) {
bestCenter = i;
}
}
int radius = p[bestCenter]; // 扩展串上的半径
int start = (bestCenter - radius + 1) / 2; // 映射回原串起始下标
int len = radius - 1; // 原串中的回文长度
return s.substring(start, start + len);
}
映射公式的推导依据是扩展串与原串的长度关系:扩展串下标 i 对应原串下标 i / 2(奇数位是分隔符)。映射中的取整方向是常见错误点,建议用一个已知答案的短串(如 "aba"、"abba"、"a")验证起始下标与长度。
4. AC 自动机实现要点
4.1 建树与 BFS 构建失配指针
class AhoCorasick {
private static final int SIGMA = 26;
private final int[][] next; // trie 图:缺失转移被补齐为 fail 链上的转移
private final int[] fail;
private final List<Integer>[] out;
private int size = 1; // 0 为根
@SuppressWarnings("unchecked")
AhoCorasick(int maxNodes) {
next = new int[maxNodes][SIGMA];
fail = new int[maxNodes];
out = new List[maxNodes];
for (int i = 0; i < maxNodes; i++) {
out[i] = new ArrayList<>();
Arrays.fill(next[i], -1);
}
}
void insert(String p, int id) {
int node = 0;
for (int i = 0; i < p.length(); i++) {
int c = p.charAt(i) - 'a';
if (next[node][c] == -1) {
next[node][c] = size++;
}
node = next[node][c];
}
out[node].add(id); // 记录模式编号,便于统计
}
void build() {
Deque<Integer> queue = new ArrayDeque<>();
fail[0] = 0;
for (int c = 0; c < SIGMA; c++) {
if (next[0][c] == -1) {
next[0][c] = 0; // 根的缺失转移指向根
} else {
fail[next[0][c]] = 0;
queue.add(next[0][c]);
}
}
while (!queue.isEmpty()) {
int u = queue.poll();
out[u].addAll(out[fail[u]]); // 输出沿 fail 链继承,避免漏掉短模式
for (int c = 0; c < SIGMA; c++) {
int v = next[u][c];
if (v == -1) {
next[u][c] = next[fail[u]][c]; // 转移继承:匹配时无需上溯
} else {
fail[v] = next[fail[u]][c];
queue.add(v);
}
}
}
}
}
四点注意:
- 节点数组需要预先确定容量(模式总字符数 + 1)。若用动态扩容或
HashMap表示转移,性能会明显下降;若字符集大,可改用HashMap<Integer, Integer>的转移表。 - 根的处理是特例。根的 fail 指向自身,根的缺失转移指向根,这一步必须在 BFS 的起点完成,否则第一层节点的转移继承会取到
-1。 out[u].addAll(out[fail[u]])的顺序。因为按 BFS 处理,fail[u]的深度更小、已经处理完毕,因此可以安全合并。- 字符归一化在插入与匹配两处必须一致。大小写、全半角、非字母字符的处理若不一致,会出现“模式已插入却匹配不到”(见第 7 小节)。
4.2 匹配时的统计与去重
// 统计每个模式在 text 中的出现次数;patternCount 为模式总数
int[] matchCount(String text, int patternCount) {
int[] count = new int[patternCount];
int node = 0;
for (int i = 0; i < text.length(); i++) {
node = next[node][text.charAt(i) - 'a']; // 一步转移,无需 while 上溯
for (int id : out[node]) {
count[id]++; // 该模式在此位置出现一次
}
}
return count;
}
两点统计语义需要明确:
- “出现次数”定义是否允许重叠。
aaaa中模式aa的重叠出现是否分别计数,必须与需求一致;上面的实现按重叠计数。 - 是否需要去重。“文本中有哪些敏感词命中”这类需求只需要模式级别的去重,可在统计后统一处理,或在输出的
out集合中使用Set。
若模式数量很大而文本很长,逐位置上报输出会成为瓶颈,此时改用差分计数:先对每个节点累加“到达次数”,再沿 fail 树自底向上把计数累加到父节点(fail 树是所有 fail 指针构成的树),一次遍历得到全部模式的次数,代价与节点总数同阶。
4.3 与其他匹配方式的对照
| 实现方式 | 构建代价 | 单次匹配代价 | 适用 |
|---|---|---|---|
| 逐位置字典树扫描 | 建树 O(Σ|p_i|) | O(n × Lmax) | 模式少、文本短 |
| AC 自动机(fail 链上溯) | O(Σ|p_i|) | O(n × 平均上溯长度 + 输出数) | 模式多;空间省 |
| AC 自动机(转移继承) | O(|Σ| × Σ|p_i|) | O(n + 输出数) | 模式多、对匹配速度敏感;空间较大 |
| 滚动哈希(按长度分组) | O(Σ|p_i|) | 期望 O(n × 长度组数) | 模式数量大但长度集中;实现简单 |
5. 复杂度与实测
5.1 复杂度对照表
以 n 为文本长度、m 为模式长度、k 为模式数量、N = Σ|p_i| 为模式总字符数、σ 为字符集大小、Lmax 为最长模式长度。
| 算法 | 预处理 | 匹配 | 空间 | 在线 | 结果规模参与复杂度 |
|---|---|---|---|---|---|
| 朴素匹配 | 无 | 最坏 O(nm),平均接近 O(n) | O(1) | 是 | 否 |
| KMP | O(m) | O(n + m) | O(m) | 是 | 否 |
| Rabin-Karp | O(m) | 期望 O(n + m),最坏 O(nm) | O(1) 或 O(n) | 是 | 否 |
| Z 函数 / 扩展 KMP | — | O(n + m)(含拼接扫描) | O(n + m) | 否(需完整串) | 否 |
| Manacher | — | O(n) | O(n) | 否 | 否 |
| AC 自动机 | O(N) 或 O(σN) | O(n + 出现数) | O(N) 或 O(σN) | 是 | 是 |
| 后缀数组(对照) | O(n) 或 O(n log n) | O(m + log n) | O(n) | 否 | 否 |
三点判读口径:
- “最坏”与“平均”的差距由输入分布决定。朴素匹配与 Rabin-Karp 的最坏情况都可被特定输入触发,而 KMP 的最坏与平均同为线性;对输入不可信的场景,确定性的最坏保证比期望值更有价值。
- 含“出现数”的复杂度是输出敏感的。AC 自动机与暴力枚举在“结果很多”时都慢,但原因不同:前者慢在输出本身,后者慢在重复比较。评估时要把“匹配计算”与“结果输出”分开。
- 空间的口径与实现绑定。AC 自动机的转移继承把空间从 O(N) 提到 O(σN),在小字符集(如小写字母 σ = 26)上是可接受的常数放大,在 Unicode 上则不可行。
5.2 实测与理论的差异
理论复杂度只给趋势,实测差异主要来自三处:
- 哈希与常数因子。滚动哈希的每次窗口滑动包含乘法与取模,常数明显大于 KMP 的一次字符比较;只有当“哈希比较替代了多次字符比较”时才有收益。取模运算在多数 CPU 上较慢,改用自然溢出(模 2⁶⁴)可显著提速。
- 缓存局部性。AC 自动机的转移表是二维数组,随机访问会频繁缺页或未命中缓存;把转移表按字符集收窄(如只支持小写字母)能提高命中率。KMP 的
pi数组很小,通常常驻缓存。 - 数据分布。随机文本上朴素匹配的表现可能优于 KMP 的常数;重复字符多的文本上差距反转。因此基准必须覆盖“随机输入”与“退化输入”两类。
微基准的编写方式、预热与死代码消除等陷阱、结果判读方式见 JMH 微基准测试。字符串算法的基准至少需要参数化四个维度:
| 维度 | 取值建议 | 观察点 |
|---|---|---|
| 文本规模 n | 10³、10⁵、10⁷ | 耗时是否随 n 线性增长 |
| 模式长度 m | 2、10、100、1000 | 预处理开销占比随 m 的变化 |
| 模式数量 k | 1、10、10³、10⁵ | 单模式算法与多模式算法的交叉点 |
| 输入分布 | 随机、周期串、单字符重复、自然语言文本 | 平均情况与最坏情况的差距 |
| 字符集 | 小写字母、ASCII、含中文 | AC 自动机转移表的空间与命中率 |
5.3 不同规模下的选择
短文本(长度 10^3 以内):
直接用语言内置的查找函数(多数实现已做常数优化),不必手写算法
中等文本、单模式、输入可信:
KMP 或内置函数;需要全部重叠位置时用 KMP
大文本、单模式、输入不可信:
KMP(最坏线性),避免依赖哈希的期望复杂度
需要同时匹配大量模式:
AC 自动机;模式集合固定时构建一次长期复用
模式数量大但长度集中、允许极小错误概率:
按长度分组的滚动哈希,实现更简单
需要任意子串的快速比较(去重、最长重复子串):
预计算前缀哈希与幂数组,O(1) 比较
回文相关问题:
Manacher;若只判定少量区间的回文,滚动哈希(正反两次)即可
6. 工程应用
6.1 日志与文本检索
日志检索的核心操作是“在一行或一批文本中查找关键词”。grep 这类工具对单次搜索使用 Boyer-Moore 式的跳跃匹配(一种支持快速跳过的单模式算法),对大量固定模式则可能构建自动机。命令行检索的语法、正则表达式与字段过滤方式见 linux: 日志查询与审计命令。
字符串算法在此场景的三处落点:
- 高亮与定位:需要返回全部匹配位置并映射到行内偏移,KMP 或内置查找足够;
- 规则匹配:一批固定规则(错误码、异常类名)可用 AC 自动机一次扫描完成,避免每条规则各扫一遍;
- 大小写与变形:日志中的大小写、空格、编码变形会影响召回,通常先归一化再匹配,归一化规则必须与建索引时一致。
6.2 敏感词与规则匹配
敏感词过滤是 AC 自动机的典型应用:词库固定、文本流式、要求单遍扫描。设计中需要明确的语义包括:
最长匹配优先:沿路径记录最后一个词节点,用于确定替换边界
最短匹配优先:遇到的第一个词节点即命中
重叠出现的处理:文本中 "abcd" 同时命中 "ab" 与 "abcd" 时,如何替换才不会漏
变形绕过:插入分隔符、全半角混用、大小写混用需要在扫描前归一化
结构层面的完整讨论(字典树与 AC 自动机的选择、词库热更新的双缓冲方案)见 字典树与字符串索引 的敏感词过滤与热更新两节。
6.3 输入校验与格式解析
输入校验(邮箱、手机号、日期、标识符)是对整个字段的模式匹配,通常不由手写算法承担,而由正则表达式或状态机完成。正则表达式的回溯代价问题见第 7.5 小节。若校验规则是固定集合且规模很大(如大量枚举值),可用字典树或 AC 自动机替代逐条正则。
一个易被忽略的前提是编码:校验前必须确认输入已经按预期字符集解码,否则多字节字符的截断会被误判为格式错误。字符与码点、UTF-8 与 UTF-16 的关系见 Java 时间处理与字符编码。
6.4 字符串相似度与模糊匹配
允许错配的匹配(拼写纠正、近似搜索、脏数据比对)不能用精确匹配算法解决,需要编辑距离或最长公共子序列这类动态规划方法:
编辑距离:把 A 变成 B 所需的最少插入、删除、替换次数
代价 O(|A| × |B|),可用滚动数组把空间降到 O(min(|A|, |B|))
若只需判断“距离是否不超过 k”,可用带阈值的剪枝把实际代价压低
最长公共子序列(LCS):两个序列共有的最长子序列,代价同量级
这些方法的共同结构是“两个序列的前缀之间的状态转移”,属于序列类动态规划的典型形态,状态定义与转移方程的完整推导见 动态规划 中序列匹配一节。在字符串场景中,它们的实用形式通常带剪枝:当剩余长度差或已知下界超过阈值时立即放弃,避免在长串上做完整的两维计算。
6.5 数据去重与指纹
去重与指纹用哈希把“内容相等”转化为“哈希相等”:
小规模、要求精确:HashSet 存原始字符串,见 [散列表](../hash/hash_table.html)
大规模、可接受极小误判:位数组上的多重散列,见 [位图与布隆过滤器](../hash/bitmap_and_bloom_filter.html)
内容指纹(文件、请求体):滚动哈希或加密摘要,取定长指纹做比对
需要区分两类等价判断:加密摘要(如 SHA-256)的碰撞概率在工程上可忽略,适合做内容指纹;滚动哈希的碰撞概率与模数、输入规模相关,在去重场景中应配合原始内容校验。二者的选择依据是“是否允许极小概率的误判”与“是否需要抵御构造攻击”。
6.6 编码与字符边界
字符串算法对“第 i 个字符”的假设,在变长编码下并不成立。三类常见错误:
1. 把字节长度当作字符长度:UTF-8 中一个中文字符占 3 字节,截断到“前 100 个字节”可能切碎一个字符
2. 按字节做模式匹配:模式与文本若不在同一边界上对齐,会出现错误的命中
3. 代理项对处理:UTF-16 中增补字符(emoji 等)占两个代码单元,
charAt 与 substring 都可能在中途切开一个字符
因此,字符串算法应在字符或码点层面工作,而字节层面的操作只用于编码与解码的边界。工程上的做法是:统一在边界处完成解码与归一化,算法内部只处理字符序列;若必须处理字节流(如超大文件、网络分片),则先做边界对齐或使用能在任意位置重新同步的编码(UTF-8 的起始字节模式可用于此)。完整的字符与编码讨论见 Java 时间处理与字符编码。
7. 常见问题与排查
7.1 下标越界与循环条件错误
现象:IndexOutOfBoundsException、StringIndexOutOfBoundsException,或结果整体少一位、多一位。
原因:KMP 的回退用错一位(pi[j] 与 pi[j-1] 混用)、Manacher 的右边界语义(开区间与闭区间)不一致、匹配结果的起始下标写成 i - m 而非 i - m + 1、模式长于文本时未提前返回。
排查:
- 用最小用例逐位打印中间状态(
i、j、pi[i]、半径数组),与手推结果对照; - 对照第 1.3 小节给出的六组边界用例,覆盖空模式、模式长于文本、完全重合、重叠出现等情况;
- 把结果与暴力匹配在同一批随机输入上的结果做全量比对(随机化对拍),这是发现下标类错误最有效的手段。
7.2 哈希冲突导致误判
现象:去重时两条不同的数据被判为同一条;子串比较偶尔返回错误结果;在数据量增大后才出现。
原因:单哈希的模数过小、base 与字符值选择不当导致构造性冲突、取模后未处理负值导致同一子串出现两种哈希值、去重时只比较哈希而未校验原始内容。
排查与修复:
- 统计哈希值的分布(不同输入映射到同一哈希的比例),评估是否偏离预期;
- 改用双哈希或增大模数;
- 关键路径上加一次逐字符校验(只对哈希相等的候选做,代价可控);
- 取模一律补正到
[0, mod); - 若输入不可信,改用带随机种子的哈希,避免被离线构造。
7.3 未处理编码与多字节字符
现象:中文、emoji 或生僻字相关的结果错误;截断后的字符串出现乱码;同一逻辑文本在不同环境下匹配结果不同。
原因:算法在字节层面工作而文本是变长编码、截断位置落在字符中间、代理项对被 charAt 切开、模式与文本的字符集不一致。
排查:确认输入解码所用的字符集、算法处理的单位(字符、代码单元还是字节)、以及截断与切分发生的位置;用包含四字节字符与混合编码的样本专门验证。字符与编码的完整分类见 Java 时间处理与字符编码。
7.4 多模式匹配输出重复或缺失
现象:同一模式被报告多次(同一位置重复输出,或同一结果被多次收集);某个模式始终不命中(尤其是另一个模式的后缀)。
原因:
- 重复:未按“模式 + 位置”去重;或多次调用匹配而结果列表未清空;或输出沿 fail 链上溯与构造时合并继承同时使用,导致同一输出被计两次。
- 缺失:未做输出沿 fail 链继承,导致短模式(作为长模式后缀的模式)没有被报告;字符归一化在插入与匹配两处不一致;转移继承中根的缺失转移未正确初始化。
排查:用包含“一个模式是另一个的后缀”(如 he、she)与“模式互为前缀”(如 ab、abc)的用例验证;检查输出的去重口径;断点确认匹配过程中经过的节点与其输出集合。
7.5 正则表达式回溯导致的性能问题
现象:某条正则规则在特定输入上耗时骤增,甚至导致 CPU 打满或请求超时。
原因:回溯型正则引擎在遇到嵌套量词(如 (a+)+)与不匹配的长输入时,会枚举大量失败路径,代价随输入长度指数增长。这与字符串精确匹配算法的“不回退”特性形成对比:KMP 与 AC 自动机的线性保证来自状态与失配跳转的设计,而朴素回溯没有这种保证。回溯的代价与剪枝的一般讨论(贪心与回溯的取舍)属于算法设计中的通用问题,见 贪心与回溯。
处理方式:
| 方式 | 做法 | 取舍 |
|---|---|---|
| 改写正则 | 用等价的、不产生嵌套量词的形式 | 需要理解回溯触发条件 |
| 限制输入长度 | 对参与正则匹配的输入设上限 | 最外层兜底,但不解决单次指数 |
| 使用 DFA 引擎 | 编译为确定有限自动机,匹配过程无回溯 | 编译开销大,部分特性(反向引用)不支持 |
| 用确定性算法替代 | 固定模式集合改用 AC 自动机,固定格式校验改用手写状态机 | 能力受限,但复杂度可控 |
| 设超时 | 对单次正则匹配设时间上限 | 只止损,不解决根因 |
对用户可控的输入使用正则时,需要把“正则的复杂度”纳入评审,而不是只关注功能正确性。
7.6 其他常见问题
| 现象 | 可能原因 | 排查方向 |
|---|---|---|
| KMP 结果与暴力匹配不一致 | 回退下标差一位、匹配成功后 j 处理错误 | 随机化对拍,逐位打印 i、j、pi[i] |
| Manacher 映射回原串的下标偏移 | 开闭区间语义混用、取整方向错误 | 用 "aba"、"abba"、"a" 验证起止下标 |
| 滚动哈希在长文本上变慢 | 每次取模运算的常数、未预计算幂数组 | 改用自然溢出;一次预计算幂数组与前缀哈希 |
| AC 自动机内存超限 | 转移表按 Unicode 大小开表 | 收窄字符集、改用映射转移表、删除无用转移 |
| 多模式匹配结果重复 | 输出未去重或重复累计 | 明确“模式级去重”与“位置级计数”的口径 |
| 同一份文本两次匹配结果不同 | 归一化规则不一致、哈希随机种子不同 | 统一归一化入口;确认哈希是否需要可复现 |
8. 检查清单
8.1 前提与语义
- 文本与模式的字符编码是否明确,算法处理的单位是字符、代码单元还是字节?
- 需要的匹配语义是否已定义:是否存在性、全部位置、是否允许重叠、是否要求最长匹配优先?
- 空模式、模式长于文本、模式与文本完全相等这三类边界的行为是否明确?
- 多模式匹配中,“模式级去重”与“出现次数统计”是否区分清楚?
8.2 算法与规模
- 是单模式还是多模式?多模式时是否已评估逐个跑单模式算法(O(k × n))的代价?
- 输入规模与模式规模处于哪一档?是否落在第 5.3 小节的选型区间内?
- 对输入是否可信?若不可信,所选算法的最坏情况是否可接受(哈希的期望复杂度不够)?
- 是否允许近似匹配?若允许,编辑距离的阈值与剪枝条件是否已设定上限?
- 需要子串的快速比较或去重时,是否评估过哈希方案与误判率?
8.3 实现与边界
- KMP 的
pi约定是否在与调用方共享的注释中写明(pi[i]的语义与下标口径)? - 滚动哈希的
base、模数、负值处理与幂数组是否统一,冲突控制是否与误判容忍度匹配? - Manacher 的右边界开闭语义、分隔符与输入冲突的可能性是否处理?
- AC 自动机的输出是否沿 fail 链继承,根的缺失转移是否初始化,字符归一化在插入与匹配两处是否一致?
- 是否有一组固定用例覆盖:重叠出现、模式互为前缀与后缀、空串、全重复字符、含多字节字符?
8.4 性能与验证
- 是否按第 5.2 小节的维度做过实测,且结论带有文本规模、模式长度、模式数量、输入分布、字符集等条件?
- 是否包含退化输入的用例(单字符重复、周期串),验证最坏情况的实际耗时?
- 是否用随机化对拍(与暴力匹配对照)验证过正确性?
- 正则参与的校验是否有回溯风险的评估与超时保护?
四、总结
问题与解法。 字符串匹配的起点是朴素匹配的重复比较:文本被反复对齐、同段的字符被多次比较。要消除这种浪费,方向只有一条——对模式或文本做一次预处理,把“失配后应从哪里继续”预先算出来,使匹配阶段不必回退。KMP 记录模式每个位置的最长相等真前缀与真后缀,失配时按这一长度平移模式,文本指针不回退;Rabin-Karp 用滚动哈希把子串比较降为常数次运算,命中后再逐字符校验;Z 函数记录每个后缀与整串的最长公共前缀,用一次线性扫描替代逐个位置的比较;AC 自动机把模式集合组织成字典树并加上失配指针,使文本只需扫描一遍。四者的共同结构是把匹配进度保存为状态、把字符读入表示为状态转移、把失配表示为状态的重新定位——这与 字典树与字符串索引 中有限状态自动机的视角一致。
复杂度的核心结论。 KMP、Z 函数与 Manacher 的线性复杂度都建立在一句相同的论证上:一个单调递增的量(已匹配长度或最右边界)只会通过回退或平移减少、且始终非负,因此回退的总量有界。这使看似嵌套的循环化为线性。相比之下,朴素匹配与 Rabin-Karp 的最坏情况可以被特定输入触发(重复字符、构造性的同哈希串),因此对输入不可信的场景,KMP 的确定性最坏保证比期望值更可靠;AC 自动机的复杂度则包含“输出规模”,需要把匹配计算与结果输出分开评估。所有这些复杂度的具体取值与推导口径,参见 复杂度与算法分析。
结构与工具的分工。 前缀查询由字典树承担,子串匹配由 KMP 族承担,回文由 Manacher 承担,多模式匹配由 AC 自动机承担,字符串集合的快速相等判定由哈希承担,文本内部的子串索引由后缀结构承担。它们共享“用结构记录字符之间的重复关系”这一思想,但索引对象不同:字典树索引字符串集合的前缀,后缀结构索引单个文本的全部子串,哈希索引的是“相等关系”本身。混用这些工具(例如用哈希承担必须严格的判等、用字典树回答任意区间查询)会带来隐蔽的缺陷,选择时应先明确查询的形态。
实现的关键点。 字符串算法的缺陷高度集中在下标与边界上:KMP 的回退下标与 pi 约定的对齐、Manacher 的右边界开闭与结果映射的取整方向、滚动哈希的负值补模与冲突控制、AC 自动机的根节点初始化与输出沿 fail 链继承。这些不是理解问题而是实现问题,处理方式是选定一种约定并写进注释、用固定的小用例覆盖边界、用随机化对拍与暴力实现比对。哈希类算法的额外要求是把“概率正确”与“严格正确”区分开:相等需要校验,不等则可直接判定。
工程落点与风险。 日志检索、敏感词过滤、输入校验、相似度匹配、数据去重与内容指纹是字符串算法的主要落点,其中三处结论值得强调:多模式匹配的吞吐由是否使用 AC 自动机决定,而召回率由是否统一处理字符变体(大小写、全半角、插入分隔符)决定,二者属于不同层面的工作;去重与指纹的正确性取决于是否区分精确与近似,凡要求严格正确的场合都必须保留一次内容校验;字符串算法的工作层面是字符而非字节,任何在变长编码下按字节截断或按字节匹配的实现都可能切碎字符,输入侧的统一解码与归一化是这一类问题的前置条件,见 Java 时间处理与字符编码。选型的判据可以收敛为一句话:先确定问题是单模式还是多模式、精确还是近似、输入是否可信,再在“确定性最坏保证”与“更小的常数”之间取舍,并用覆盖退化输入的实测确认结论。