字符串匹配进阶路线 ​

本部分我们学习了字符串匹配的核心算法。这一章做一个总结，并展望更高级的算法，为有志深入学习的读者指明方向。

本部分回顾 ​

我们已经掌握的内容：

朴素字符串匹配

• 思路：从每个位置开始逐字符比较
• 复杂度：O(n×m) 最坏，O(n) 平均
• 特点：简单直观，适合短字符串

KMP 算法

• 核心：利用已匹配信息，通过 next 数组跳过重复比较
• 复杂度：O(n+m)
• 特点：稳定高效，单模式匹配首选

字符串哈希

• 思路：将字符串映射为数字
• 特点：O(1) 比较子串，预处理后 O(1) 计算任意子串哈希

Rabin-Karp 算法

• 核心：滚动哈希 + 滑动窗口
• 复杂度：O(n+m) 期望
• 特点：实现简单，易于扩展到多模式匹配

这些算法足以应对绝大多数面试题和实际场景。但字符串算法是一个深广的领域，还有很多精妙的算法等待探索。

进阶算法预览 ​

Z 函数（扩展 KMP） ​

功能：计算每个位置与原字符串的最长公共前缀长度。

s = "aabxaab"
z = [7, 1, 0, 0, 3, 1, 0]

z[4] = 3 表示 s[4..] = "aab" 与 s 的最长公共前缀是 "aab"，长度 3

应用：

• 字符串匹配的另一种方法
• 周期检测
• 最小循环节

复杂度：O(n)

AC 自动机（Aho-Corasick） ​

功能：在文本中同时查找多个模式串。

原理：Trie + KMP 思想。在 Trie 上构建失配指针，实现多模式同时匹配。

应用：

• 敏感词过滤
• 病毒特征码检测
• 多关键词搜索

复杂度：预处理 O(Σm)，匹配 O(n + 出现次数)

后缀数组（Suffix Array） ​

定义：将字符串的所有后缀排序后的索引数组。

s = "banana"
后缀：banana, anana, nana, ana, na, a
排序：a, ana, anana, banana, na, nana
SA = [5, 3, 1, 0, 4, 2]

应用：

• 最长公共子串
• 重复子串统计
• 字符串排名

复杂度：构建 O(n log n) 或 O(n)，配合 LCP 数组功能更强

后缀自动机（SAM） ​

定义：接受字符串所有后缀的最小确定有限自动机。

特点：

• 状态数和边数都是 O(n)
• 能高效处理子串相关问题

应用：

• 本质不同子串计数
• 最长公共子串
• 子串出现次数

复杂度：O(n)

Manacher 算法 ​

功能：O(n) 找出字符串中所有回文子串。

核心：利用已知回文的对称性，跳过不必要的比较。

应用：

• 最长回文子串
• 统计回文子串数量

复杂度：O(n)

学习路线建议 ​

根据你的目标选择学习路线：

面试准备路线 ​

基础（已学）→ Manacher（回文题常考）→ Z 函数（选学）

重点掌握 KMP 和 Rabin-Karp，能手写代码、清晰解释原理。Manacher 在回文相关题目中很有用。

算法竞赛路线 ​

基础 → Z 函数 → 后缀数组 → 后缀自动机 → AC 自动机

竞赛中字符串题难度较高，需要系统学习这些高级数据结构。

工程应用路线 ​

基础 → 正则表达式深入 → 全文搜索引擎原理

实际工程中，通常使用成熟的库和框架。了解底层原理有助于性能优化和问题排查。

算法复杂度对比 ​

推荐资源 ​

在线学习：

• OI Wiki：https://oi-wiki.org/string/
• CP-Algorithms：https://cp-algorithms.com/string/

经典教材：

• 《算法导论》第 32 章：字符串匹配
• 《算法》第四版：第 5 章字符串

练习平台：

• LeetCode 字符串专题
• Codeforces 字符串标签题目

本章小结 ​

字符串算法是算法领域的重要分支。本部分覆盖了最核心的基础算法：

• 朴素匹配：理解问题本质
• KMP：利用已匹配信息优化
• 字符串哈希：将比较问题转化为数值计算
• Rabin-Karp：哈希 + 滑动窗口

这些算法思想不仅适用于字符串，在其他领域也有广泛应用。

对于更高级的算法，建议根据实际需求选择性学习。记住：理解原理比背诵代码更重要。

下一部分，我们将进入哈希表的学习，它是另一个重要的基础数据结构。