SAM 应用

关于本文中的符号的定义，参见《后缀自动机与后缀树》一文的摘要。

A 简单应用

两个后缀 LCP

后缀树

就是两个结点在 fail 树上的 LCA。

本质不同的子串个数

后缀树

设 $\ell(q)$ 表示等价类 $q$ 中最长的字符串的长度，也就是通常称的 $\text{len}(q)$ 。则显然 $|q|=\ell(q)-\ell(\theta(q))$ 。因此 $s$ 的本质不同子串个数为

$\sum_{q\in Q,q\ne q_0}\ell(q)-\ell(\theta(q))$

字典序第 k 小子串

SAM

多组询问，查询 $s$ 的子串中字典序第 $k$ 小的子串。

遇到字典序最小的问题，就不太能用后缀树求解。因此我们直接利用 $\delta$ ，在 SAM 上 DFS 一遍即可。

复杂度 $O(|S||\Sigma|)$ 。

匹配同构串

询问在串 $s$ 中出现了多少次 $x$ 的循环同构串。

SAM

首先对 $s$ 建 SAM，然后先在 SAM 上跑一遍 $x$ 。再接着跑一遍，这次就可以记录答案了。我们记录一个当前匹配的长度，对 $x$ 的长度取 min。这样我们就可以判断当前结点包含的状态中是否有 $x$ 的循环同构串。有一个贪心的想法就是，每次走了一个字符，就贪心地跳 fail，要求 fail 的长度也大于等于当前匹配长度。因为 fail 的转移指针是包含它的儿子结点的。然后加上当前状态的出现次数即可。

CF 234C

B 进阶套路

B1

设 $f(i)$ 为所有长度为 $i$ 的子串的出现次数的最大值，求 $f(1),f(2),\cdots,f(|S|)$ 。 $|S|\le 250000$ 。

SAM 可以算出每个子串的出现次数。对于结点 $u$ ，相当于区间 $[\ell(\theta(u))+1,\ell(u)]$ 的答案对 $cnt(u)$ 取 $\max$ 。

事实上没有这么复杂。由于 $f(i)\ge f(i+1)$ ，因此可以把区间左端点置为 $1$ ，也就是个前缀 $\max$ 。扫一遍即可。

时间复杂度 $O(n)$ 。

B2

维护串 $S$ ，支持
在末端添加一个字符
询问 $T$ 在 $S$ 中的出现次数。
$\sum |T|,Q\le 10^5$ 。

显然，我们需要动态维护 Fail 树，支持：

添加一个叶子结点 / 中间多一个结点
查询子树和

可以直接 LCT。但这题动态性较弱，可以平衡树维护 DFS 序来做。

离线的话直接把整个 SAM 建出来，然后询问离线搞一下就行。

B3

给定串 $T$ 。对于串 $s$ ，定义它的权值是至少需要几个 $T$ 的子串拼起来得到。拼不出来就是 $-1$ 。求长度为为 $n$ 的权值最大的串的权值。
$n\le 10^{18},1\le |T|\le 10^5,|\Sigma|\le 4$ 。

对于一个串 $s$ ，如何计算它的权值？

它满足贪心条件，我们贪心地匹配 $T$ 的子串直到不能匹配，就断开。

假设分成 $k$ 段 $s_1\cdots s_k$ ，那么有 $\forall s_i\in T, s_i(s_{i+1}[1])\notin T$ 。

于是我们设 $w(x,y)$ 表示最短的串 $s$ 使得 $s[1]=x,s\in T,sy\notin T$ 的长度。显然可以瞎搞搞出来。

然后用它二分 + 矩乘即可得到答案。这是双 log 的。

把二分改成倍增就是单 log。

B4

给定字符串 $S$ ，对于每个 $k$ ，求把 $S[k]$ 变成#后，本质不同的 $S$ 的子串的个数。
$1\le |S|\le 10^5$ 。

容斥，我们要求的就是 $S[1,k-1]$ 的本质不同数， $S[k+1,|S|]$ 的本质不同数， $S[1,k-1],S[k+1,|S|]$ 的公共本质不同子串数。前两者可以正着倒着建 SAM 求出。

对于后者，我们考虑每个 SAM 结点的贡献。

对于每个结点 $u$ ，我们求出它出现的最左边和最右边的位置，分别记为 $L,R$ 。

那么对于 $x\in (\ell(\theta(u)),\ell(u)]$ ，区间 $[L+x,R-1]$ 的答案就会加 $1$ 。

差分一下，就变成了 $x\in (\ell(\theta(u)),\ell(u)]$ ， $L+x$ 的加 $1$ ， $R$ 的减 $1$ 。

二次差分就变成纯单点了。

这样，总复杂度就是 $O(|S||\Sigma|)$ 的。

B5 线段树维护 Right 集合

所谓的 Right 集合是指一个状态 $q$ 在原串中所有出现的位置的集合。

与求子串出现次数类似，我们在构建 SAM 的时候每次在 last 结点的集合里插入一个位置。然后建完 SAM 后线段树合并一下即可。

C

HEOI2016 字符串

给定字符串 $s$ 和 $q$ 个询问，每个问题形如 $a, b, c, d$ 四个参数，询问 $s[a,b]$ 的所有子串和 $s[c,d]$ 的 LCP 的长度的最大值。
$1 \le n, q \le 10^5$ 。

首先把串翻转，问题转化为 $s[a,b]$ 的子串与 $s[c,d]$ 的 LCS 的长度的最大值。

也就是说我们想知道 $s[c,d]$ 的最长的被包含在 $s[a,b]$ 中的后缀。二分转化为判定问题。判定问题可以使用线段树维护 Right 集合来解决。

时间复杂度 $O(n\log_2^2n)$ 。

参考文献

OIWIKI. 后缀自动机 (SAM). https://oi-wiki.org/string/sam/

文章目录