Skip to content

06-字符串.md

Latest commit

 

History

History
328 lines (203 loc) · 7.23 KB

06-字符串.md

File metadata and controls

328 lines (203 loc) · 7.23 KB
Raw

第六章 字符串

1. 学习目标

字符串算法的核心是高效比较、匹配和统计子串结构。

你需要建立两个意识：

  1. 字符串题通常是在处理“相等关系”和“前后缀关系”。
  2. 很多结构的本质是在复用前缀信息或自动机状态。

2. 字符串哈希

2.1 基本思想

把字符串看作某一进制下的数。

设字符串为 (s_1s_2\dots s_n)，取底数 (B)、模数 (M)，则前缀哈希定义为：

[ H[i] = (H[i-1]\cdot B + val(s_i)) \bmod M ]

子串 ([l,r]) 的哈希值为：

[ hash(l,r)=H[r]-H[l-1]\cdot B^{r-l+1} ]

再对模数取正。

2.2 单哈希与双哈希

单哈希有碰撞概率。

双哈希使用两个不同模数：

[ (H_1,H_2) ]

可显著降低碰撞风险。

2.3 使用场景

  • 判断两个子串是否相等。
  • 最长公共前缀二分。
  • 回文判断。

3. 单串匹配与回文

3.1 KMP

KMP 用 next 或 pi 数组维护模式串前后缀匹配信息。

设 pi[i] 表示前缀 s[1..i] 的最长真前后缀长度。

转移核心：

当 (s_{i+1}\ne s_{j+1}) 时，令

[ j = pi[j] ]

直到可以匹配或 (j=0)。

匹配复杂度：

[ O(n+m) ]

3.2 Z 算法

z[i] 表示从 i 开始的后缀与整个串的最长公共前缀长度。

复杂度 (O(n))。

适用于：

  • 批量求 LCP；
  • 扩展 KMP；
  • 模式比较。

3.3 Manacher

用于在线性时间内求最长回文子串。

通过在原串中插入分隔符，把奇偶长度回文统一处理。

设 p[i] 表示以 i 为中心的回文半径，则复杂度：

[ O(n) ]

4. 多串匹配与自动机

4.1 Trie

Trie 按字符逐层建树。

适合：

  • 字典查询；
  • 前缀统计；
  • 字符串集合维护。

若字符集大小为 (\Sigma)，总长度为 (L)，则建树复杂度为：

[ O(L) ]

4.2 AC 自动机

AC 自动机 = Trie + 失配指针。

失配指针含义：当前匹配失败时跳转到的最长可匹配后缀状态。

其思想与 KMP 类似。

总匹配复杂度通常为：

[ O(\text{文本长度}+\text{模式串总长度}+\text{匹配次数}) ]

fail 树：把每个状态的 fail 指针看作父边，所有状态构成一棵以根为根的树。关键性质：

  • 文本中某模式串的出现位置 = 沿 AC 自动机转移到的状态在 fail 树上的祖先链。

因此「每个模式串在文本中出现几次」等价于「fail 树上以该模式串状态为根的子树中，被文本访问过的状态数」。套路：

  • 对 fail 树做 DFS 求出 dfn 序与子树区间；
  • 文本每个访问状态在 dfn 序上单点 +1；
  • 子树区间求和即可得每个模式串出现次数。

4.3 回文自动机 PAM

PAM 又称回文树。

每个结点表示一种本质不同的回文子串。

适合统计：

  • 不同回文子串个数；
  • 每种回文出现次数；
  • 回文相关 DP。

5. 高级后缀结构

5.1 后缀数组 SA

后缀数组是所有后缀排序后的编号数组。

设：

  • sa[i]：排名第 i 的后缀起始位置；
  • rk[i]：后缀 i 的排名；
  • height[i]：sa[i] 与 sa[i-1] 的最长公共前缀。

倍增算法核心思想：

把长度为 (2^k) 的关键字拆为两个长度为 (2^{k-1}) 的块排序。

常见复杂度：

[ O(n\log n) ]

height 数组应用：

height[i] 是排名第 i 与第 i-1 的后缀的最长公共前缀。重要性质：

[ lcp(sa[i], sa[j]) = \min_{i < k \le j} height[k] ]

即任意两名后缀的 LCP 等于它们在 height 数组上对应区间的最小值（可由单调栈 / ST 表维护）。

应用：

  • 本质不同子串数：

[ \frac{n(n+1)}{2} - \sum_{i=1}^{n} height[i] ]

  • 最长重复子串：max(height[i])。
  • 重复出现至少 k 次的子串：在 height 上滑动窗口求长度 k-1 区间最小值的最大值。
  • 两子串 LCP：排名区间 RMQ。

5.2 后缀自动机 SAM

SAM 中每个状态对应一类 endpos 等价类。

常见属性：

  • len：该状态表示的最长串长度；
  • link：后缀链接。

关键性质：

若状态 (p) 的后缀链接为 (link(p))，则它对应的最短串长度为

[ len(link(p)) + 1 ]

SAM 可用于：

  • 不同子串个数；
  • 子串出现次数统计；
  • 最长公共子串。

不同子串个数公式：

[ \sum_{state} (len[state] - len[link[state]]) ]

5.3 广义 SAM

广义 SAM 用于多串情形，维护多串的所有子串。

构造方式：

  • 每插入一个新串前，把 last 重置为根 1，再逐字符插入（与单串 SAM 相同）；
  • 或在 Trie 上 BFS，按父状态插入建广义 SAM。

应用：

  • 多串本质不同子串数；
  • 多串最长公共子串（在每个串对应状态上维护 endpos 出现信息，取所有串都出现的最大 len）；
  • 多串子串匹配。

注意：直接逐串重置 last 的简单写法在插入时需处理「转移已存在」的情形，避免重复建状态。

6. 常见比较

6.1 KMP vs 哈希

  • KMP：严格无碰撞，适合精确匹配。
  • 哈希：实现灵活，适合子串比较和二分。

6.2 SA vs SAM

  • SA 更偏静态排序和后缀区间问题。
  • SAM 更偏在线构造和子串统计。

6.3 Trie / AC 自动机

  • Trie 处理前缀集合。
  • AC 自动机处理多模式串匹配。

7. 常见错误

  • 哈希未统一处理负数。
  • KMP next 数组下标混乱。
  • AC 自动机构建失配指针后忘记补全转移。
  • SA 中 height 与 rk 对应关系写错。
  • SAM clone 状态复制不完整。

8. 经典题单

8.1 哈希 / KMP / Z / Manacher

  1. Luogu P3370 【模板】字符串哈希。
  2. HDU 1711 Number Sequence。
  3. Codeforces 432D Prefixes and Suffixes。
  4. Luogu P3805 【模板】Manacher。

8.2 Trie / AC 自动机 / PAM

  1. Luogu P2580 于是他错误的点名开始了。
  2. HDU 2222 Keywords Search。
  3. Luogu P5496 【模板】回文树 / 回文自动机（PAM）。
  4. Luogu P5357 【模板】AC 自动机（二次加强版 / fail 树）。

8.3 SA / SAM / 广义 SAM

  1. Luogu P3809 【模板】后缀排序。
  2. SPOJ SUBST1 New Distinct Substrings。
  3. SPOJ LCS Longest Common Substring。
  4. Codeforces 235C Cyclical Quest。
  5. Luogu P6139 【模板】广义后缀自动机（广义 SAM）。

9. 复习建议

推荐顺序：

  1. 哈希、KMP、Z。
  2. Manacher。
  3. Trie、AC 自动机（含 fail 树）。
  4. SA（含 height 应用）、SAM。
  5. 广义 SAM、PAM。

模板清单建议至少包括：

  • 字符串哈希
  • KMP
  • Z 函数
  • Manacher
  • Trie
  • AC 自动机（含 fail 树子树统计）
  • 后缀数组（含 height）
  • 后缀自动机
  • 广义 SAM
  • 回文自动机