10. 字符串结构

0. 本章先解决什么问题

字符串不是“字符数组”这么简单。很多实际问题都围绕字符串:

• 搜索关键词。
• 判断前缀。
• 自动补全。
• 路由匹配。
• 敏感词匹配。
• 文本编辑。
• 文件路径。
• DNA 序列。
• 日志扫描。

本章要解决:

• 字符串匹配为什么不能总是暴力比较?
• 前缀表和 KMP 的直觉是什么?
• 前缀树为什么适合前缀查询?
• 自动机为什么适合多模式匹配?
• 字符串结构在实际系统中怎么用?

这张图怎么读

这张图把字符串结构的共同思想画出来:不要每次从头比较。Trie 复用公共前缀,KMP/自动机复用已经知道的前后缀和状态,多模式匹配则把许多关键词合成一个状态转移过程。

1. 字符串的成本来源

字符串操作常见成本:

字符串 key 的哈希也不是免费,通常要扫描字符。

所以处理大量字符串时,结构和算法非常重要。

2. 朴素匹配

在文本中找模式串。

text = ababcabc
pattern = abc

朴素方法:

从 text 每个位置开始
逐字符比较 pattern
不匹配就移动一个位置

最坏成本:

O(n * m)

其中 n 是文本长度,m 是模式串长度。

如果文本和模式有很多重复前缀,朴素方法会做大量重复比较。

3. KMP 的核心直觉

KMP 解决的问题:

匹配失败时,不要把已经知道的信息全部丢掉。

例如模式串:

abab

当匹配到一部分失败时,前面已经匹配过的内容里可能包含可复用的前缀。

KMP 预处理模式串,构造前缀信息:

到当前位置为止
最长的“既是前缀又是后缀”的长度是多少

匹配失败时,根据这个信息移动模式串,而不是文本指针回退。

核心收益:

文本指针不回退
总匹配成本 O(n + m)

4. 前缀表理解

前缀表记录的是:

pattern[0..i] 中
最长相等前后缀长度

例子:

pattern = ababa

部分前后缀关系:

a
aba

如果已经匹配 ababa 的一部分,失败时可以跳到此前缀位置继续。

KMP 难在实现细节,但思想很简单:

利用模式串内部重复结构,避免重复比较。

手推 KMP:失败时到底跳到哪里

以模式串 ababaca 为例。它里面有重复结构:

前缀: a, ab, aba…
后缀: …a, …ba, …aba

如果已经匹配到:

ababa

下一位失败,朴素做法会把模式串整体右移一格,文本指针也可能回退。KMP 的想法是:既然 ababa 的后缀 aba 也是前缀,那就保留这部分已知匹配:

已匹配: a b a b a
可复用:     a b a

于是模式串不用从头开始,直接跳到“最长可复用前缀”的长度继续。这就是前缀表的意义:它不是神秘数组,而是在告诉你失败时最多能保留多少已知匹配。

KMP 的不变量是:

文本指针不回退
模式指针根据前缀表回退

所以总成本能保持在线性级别。

5. 前缀树 Trie

前缀树把字符串按字符路径存储。

词集合:

cat
car
dog

Trie 示意:

每条从根到某节点的路径代表一个前缀。

适合:

• 判断某词是否存在。
• 判断某前缀是否存在。
• 自动补全。
• 字典匹配。
• 路由前缀匹配。

6. Trie 的成本

如果字符串长度是 L:

成本不直接依赖词典总数量,而依赖字符串长度。

代价:

• 节点多。
• 指针或映射开销大。
• 字符集大时空间压力明显。

优化方式:

• 压缩 Trie。
• 用数组存小字符集。
• 用映射存稀疏字符集。
• 只保存必要字段。

7. 字典树和哈希表的区别

如果只查完整 key,哈希表常更简单。

如果大量前缀操作,Trie 更合适。

8. 多模式匹配和自动机

如果要同时匹配很多模式串:

bad
evil
danger
…

逐个模式跑一遍匹配会很慢。

多模式自动机的思想:

把多个模式串建成状态机
扫描文本一次
根据字符转移状态
遇到输出状态就命中某些模式

它常用于:

• 敏感词匹配。
• 入侵检测。
• 日志规则匹配。
• 多关键词搜索。

你不必一开始掌握所有构造细节,但要知道:

自动机把“匹配过程”变成“状态转移”。

9. 后缀相关结构

更高级的字符串问题会用后缀数组、后缀树、后缀自动机等结构。

它们适合:

• 子串查询。
• 重复子串。
• 最长公共子串。
• 大规模文本索引。

这些结构实现复杂,学习初期先掌握使用场景:

如果问题大量围绕“任意子串”,可能需要后缀结构。

10. 字符编码边界

字符串结构要小心字符编码。

问题:

一个用户感知字符可能不是一个 byte。

如果按 byte 建 Trie,适合处理编码后的字节序列。
如果按字符建 Trie,要先明确字符单元是什么。

实际系统中必须确认:

• 输入编码。
• 大小写规则。
• 规范化规则。
• 字符和字节长度。
• 是否支持多语言。

边界条件:同一个“看起来相同”的字符串,底层可能不同

字符串结构最怕把“显示效果”当作“存储表示”。例如:

如果 Trie 插入前按一种规则处理,查询前按另一种规则处理,就可能走到不同路径。稳妥做法是先定义规范化边界:

输入进入系统时统一编码/大小写/规范化
结构内部只处理规范化后的 token
输出时再按展示需求处理

这不是语言细节,而是字符串数据结构正确性的前提。

11. 联系实际:自动补全怎么选结构

自动补全需求:

输入前缀
返回候选词

Trie 思路:

1. 从根沿前缀字符走到对应节点。
2. 从该节点向下遍历候选词。
3. 按频率、时间或权重排序。

如果候选很多,还要结合:

• 每个节点保存 top candidates。
• 频率统计。
• 权重更新。
• 内存压缩。
• 分页或限制返回数量。

这就是字符串结构和实际产品需求的连接。

设计卡:自动补全和敏感词匹配不是同一个问题

两个需求都处理字符串,但结构选择不同:

还要特别检查编码边界:

按 byte 建结构
-> 简单直接,适合协议/二进制/已编码输入

按字符建结构
-> 要处理 Unicode、大小写、规范化、组合字符

字符串结构最容易犯的错,是只看“能不能查到”,忽略了输入规模、字符集、前缀/子串语义和更新频率。

12. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 字符串操作为什么可能很贵?
2. 朴素子串匹配为什么最坏 O(n*m)?
3. KMP 如何利用前缀信息避免重复比较?
4. Trie 为什么适合前缀查询和自动补全?
5. Trie 和哈希表如何选择?
6. 多模式匹配为什么适合用自动机思想?
7. 字符编码为什么会影响字符串结构?
8. 自动补全、敏感词匹配、路由匹配分别适合什么结构?

字符串结构的核心是复用已知前缀、后缀或状态信息,减少重复比较。

延伸阅读

• from - zero · data-structures
• String