字符串算法专题

学“字符串算法专题”时，我走过的弯路可以概括成一句话：我以前觉得字符串题无非是逐字符比较，后来遇到长文本、多模式和回文问题，才发现重复比较才是最大的浪费。问题不在于知识点有多难，而在于我一开始只盯着结果，没有看到它在维护什么关系。下面是我重新补这块基础时留下的笔记。

字符串算法专题负责处理“字符序列里的匹配、前缀、回文、多个模式和全局子串关系”。它看起来公式多，但核心其实是减少重复比较。

学字符串算法时，建议先抓住一个主线：暴力匹配哪里重复了？下一种算法复用了什么历史信息？

从 Ctrl+F 的朴素做法开始

在一篇长文中查找关键词，最直接的方法是从每个位置重新逐字比较。问题在于：前面已经比较过的字符信息被全部丢掉了。KMP 保存模式串的前后缀关系，字符串哈希保存子串摘要，AC 自动机共享多个关键词的前缀，Manacher 复用回文的镜像范围。

开始时先把字符串当成字符数组，能写出暴力匹配并明确重复工作发生在哪里，再学习优化会自然很多。

我为什么先补这一章

这一章重点解决：

1. 单模式匹配怎么优化。
2. 多模式匹配为什么需要 Trie 和 fail 指针。
3. 回文问题如何线性处理。
4. 后缀结构如何描述全局子串关系。

我自己的学习顺序

1. 字符串算法：从匹配到自动机。
2. KMP 与字符串哈希。
3. 字符串进阶算法地图。
4. AC 自动机。
5. Manacher。
6. Z 函数与后缀数组入门。

我当时最容易混淆的地方

KMP 复用的是模式串自己的前后缀信息；字符串哈希复用的是子串摘要；AC 自动机复用的是多个模式串之间的前缀关系；Manacher 复用的是回文的镜像关系。

这些算法不是都要背到滚瓜烂熟，但至少要知道它们各自解决什么类型的问题。

我后来这样检查自己是否真的理解

• KMP 的 next 数组到底表示什么？
• 字符串哈希为什么需要考虑冲突？
• AC 自动机为什么适合敏感词检测？
• Manacher 为什么能做到线性时间？