SA, SAM 重谈

字符串目前在 2025-2026 赛季的出现：CSP-S2025T3 ACAM/Trie，CTT2025D1T2 Runs，联合省选 D1T2 kmp 自动机。其中 kmp 自动机甚至数据范围允许暴力。不过因为不考就不研究这也太 utilitarian 了。

SA 和 SAM 也算是体现了很多字符串算法的核心思想，通过 \(O(n)\) 级别的前/后缀信息表达 \(O(n^2)\) 级别的子串信息。Suffix String Structures 基本都是通过建立后缀之间的关系刻画所有子串的关系。

SA

最小表示法：求 \(S\) 的最小表示法，对 \(SS\) 后缀排序即可。但是被 Duval 爆完了，不过不失为一种简单的解决方式。

优秀的拆分 trick：针对于循环子串问题，虽然大多数时候直接套 Runs 更无脑，但部分情况下复杂度更优。

比较子串大小：即求后缀 LCP，然后比较下一个字符大小。疑似被哈希二分爆完了。

---

很多题目需要在 rk 轴上考虑 height，然后变成数据结构题。

由于后缀 LCP 等价于 height 区间最小值，较为常见的是笛卡尔树单调栈等结构处理区间最小值信息。

并查集：常见形式是两个后缀对答案的贡献与 LCP 有关，这时可以枚举 LCP \(=k\)，从大到小合并相邻的两个 LCP \(\geq k\) 的后缀，利用启发式合并+数据结构维护贡献。

---

接下来给一个比较 conprehensive 的例题。

e.g. 某模拟赛-简单的字符串题

定义二元函数 \(F(x,y)\)，当 \(x\geq y\) 时 \(F(x,y)=0\)，否则 \(F(x,y)\) 为二元二次函数。

给定字符串 \(S\)，求 \(\sum F(|i-j|,l)\)，其中 \(l\) 为后缀 \(i,j\) 的 LCP。

---

使用上面并查集的 trick 加上线段树合并可以做到 \(O(n\log n)\)，但是谁写谁享受常数也不小。

注意到当 \(|i-j|\geq k\) 时 \(F(|i-j|,l)=0\)，不妨设 \(d=j-i>0\)，然后枚举 \(d\)，则 \(l>d\)。类似于优秀的拆分，在 \(d,2d,3d,\cdots\) 的位置设置哨兵，求 \(kd,(k+1)d\) 向前与向后的 LCS/LCP，可以求出包含 \(kd\) 的最长串 \(S[L:R]\) 满足 \(S[L:R]=S[L+d:R+d]\)。此时容易发现 \(\forall i\in[\max(L,(k-1)d+1),\min(kd,R)],\operatorname{LCP}(i,i+d)=R-i+1\)，于是可以统一计算 \(i\in((k-1)d,kd],j=i+d\) 的贡献。时间复杂度是调和级数 \(O(n\log n)\)。

SAM

SAM 实际上可以接受所有子串，所以建议改名子串自动机（？）。作为类比，kmp 自动机实际上是前缀自动机。在实际运用中也可以发现 SAM 常常被用于处理子串匹配问题。

大多数广义 SAM 的题都可以拼起来跑 SAM 解决，所以一般很少写广义 SAM。

---

SAM 最直接的应用就是在自动机上做子串匹配，这个一般比较简单，因为完全可以将 SAM 看作一个黑盒。

很多题是在 parent 树（后缀链接树）上做范围修改查询，基本都是检验 ds 基础题。

还有一些考察对 SAM 理解的题，属于是专杀背板子选手。其实如果对 kmp 自动机+失配树 有一个比较深刻的理解应该很容易解决一些 essential 的 SAM 理解问题。搞明白之后甚至可以尝试自己手搓 PAM（）。

举个例子，所有右端点相同的子串在 SAM 上表现为 parent 树的一条根链，所有左端点相同的子串在 SAM 上表现为一条转移图上的链。会有走 parent 树在左边删字符，走自动机在右边加字符的说法。

有一个不得不品的题目是 [候选队互测2022]可爱多的字符串，根号做法和常规双老哥做法都很 enlightening。如果难度跨度太大可以先品 CF1098F Ж-function。