字符串算法在竞赛中的出现频率越来越高，本文带你系统掌握核心字符串算法。
一、字符串哈希（Hash）
最简单实用的字符串匹配方法。
- 将字符串映射为一个整数
- 使用前缀和 O(1) 求任意子串的哈希值
- 双哈希减少碰撞概率
- 常用模数：1e9+7, 1e9+9, 998244353
二、KMP 算法
线性时间的单模式串匹配：
// 计算 next 数组
for (int i = 2, j = 0; i <= m; i++) {
while (j && p[i] != p[j+1]) j = nxt[j];
if (p[i] == p[j+1]) j++;
nxt[i] = j;
}
// 匹配过程
for (int i = 1, j = 0; i <= n; i++) {
while (j && s[i] != p[j+1]) j = nxt[j];
if (s[i] == p[j+1]) j++;
if (j == m) { 匹配成功; j = nxt[j]; }
}三、字典树（Trie）
用于存储和快速检索字符串集合：
- 插入和查询复杂度 O(L)，L 为字符串长度
- 01-Trie：处理异或最值问题的利器
- 可持久化 Trie
四、AC 自动机
KMP + Trie = AC 自动机，用于多模式串匹配：
- 构建 Trie 树
- 计算 fail 指针（失配时跳转到哪）
- 在文本串上遍历，每步跳转 fail 指针
五、Manacher 算法
线性时间求最长回文子串，代码极短但原理抽象。
六、后缀数组（SA）与后缀自动机（SAM）
进阶内容，NOI 级别考点：
- SA：O(n log n) 构建，配合 height 数组
- SAM：O(n) 构建，解决子串相关问题
推荐练习：
- KMP：洛谷 P3375
- Trie + 01-Trie：洛谷 P4551 最长异或路径
- AC 自动机：洛谷 P3808
- Manacher：洛谷 P3805
暂无评论，快来抢沙发吧~ 🛋️