字符串进阶算法地图：多模式、回文与后缀结构

如果只看定义，“字符串进阶算法地图：多模式、回文与后缀结构”并不一定显得难。我当时真正卡住的是：多模式匹配、回文和后缀结构的名字很多，我曾经挨个看定义，最后仍然不知道遇到问题时应该往哪个方向想。这次整理没有刻意追求一次讲完所有技巧，而是把我最容易断掉的几个理解环节重新接上。

字符串算法前面已经讲过 KMP 和字符串哈希，这篇作为进阶总览，把多模式匹配、回文、前缀函数和后缀结构放到同一张地图里。学字符串不要一上来就背一堆名字，而要先判断题目到底在问哪类关系。

先按问题类型选算法

图：多模式匹配、回文、前缀匹配、全局子串关系分别对应不同工具

常见字符串问题可以粗略分成四类：

问题	常用算法
一个模式串匹配一个文本	KMP、字符串哈希
多个模式串同时匹配文本	Trie、AC 自动机
回文子串、最长回文	中心扩展、Manacher
所有后缀、重复子串、字典序	后缀数组、后缀自动机入门

为什么字符串题容易混乱

字符串题容易写乱，是因为同样是“匹配”，背后目标可能完全不同。

比如：

• 判断 pattern 是否出现在 text 中：KMP 足够。
• 在文本中检测一万个敏感词：KMP 一个个跑会重复，AC 自动机更合适。
• 求最长回文子串：KMP 不是首选，Manacher 更贴合。
• 求最长重复子串：需要比较大量后缀，后缀数组或哈希 + 二分更自然。

字符串算法的共同思想

虽然名字不同，但它们共同在做一件事：减少重复比较。

• KMP：失配后复用模式串前缀信息。
• AC 自动机：多个模式串共享 Trie 前缀，失配后沿 fail 指针跳转。
• Manacher：利用回文中心的镜像关系减少重复扩展。
• 字符串哈希：把子串比较变成数值比较。
• 后缀数组：把所有后缀排序后，相邻后缀更容易比较公共前缀。

学习顺序

建议顺序如下：

1. 暴力匹配：先知道慢在哪里。
2. KMP：理解失配跳转和 next 数组。
3. Trie：理解前缀共享。
4. AC 自动机：理解 fail 指针如何让 Trie 能在文本上流动。
5. Manacher：专门处理回文。
6. Z 函数：理解字符串与自身前缀的匹配长度。
7. 后缀数组：建立“把所有后缀拿出来排序”的全局视角。

工程场景

字符串进阶算法在工程中并不只是刷题：

• 敏感词检测：Trie / AC 自动机。
• 搜索建议：Trie、倒排索引。
• 日志规则匹配：多模式匹配。
• DNA 序列分析：字符串匹配与公共子串。
• 文本去重：字符串哈希、SimHash 等思想。
• 搜索引擎：分词、倒排索引、相关性排序。

我的分析

字符串题最重要的是先识别“比较对象”。一个模式串对一个文本，可以走 KMP；很多模式串对一个文本，就不要傻傻多次 KMP；如果问题和回文有关，中心对称性才是核心；如果涉及所有子串或后缀之间的关系，就要进入后缀结构。

这篇总览的目的不是让你一次吃完所有字符串算法，而是之后遇到题时知道应该往哪个方向想。

面试题

1. KMP 和 AC 自动机分别适合什么匹配场景？
2. 为什么 AC 自动机需要 fail 指针？
3. Manacher 解决的是哪类问题？
4. 字符串哈希有什么风险？
5. 后缀数组为什么适合处理重复子串和字典序问题？