后缀数组/后缀自动机/广义后缀自动机简单应用
FutaRimeWoawaSete
·
·
个人记录
来背了哥
以下简写 height 为 ht。
个人习惯是将字符串从 1 开始标号。
问题基本选自 OI-WIKI 以及论文。
由于后缀数组/SAM实在是博大精深，所以每种问题解法不一，下文提供的解法仅作参考。
1
将大小为 n 的字符串循环位移得到 n 个新的字符串，求这 n 个字符串的排序情况。
Sol
应该还是要保证 n 个字符串构成的是个偏序集。
考虑 copy 原串后直接进行后缀排序即可。
2
在文本串中寻找匹配串。
Sol
设 S 为文本串，T 为匹配串，则有一种预处理 O(|S| \log |S|)，单次查询 O(T \log |S|) 的做法。
考虑二分后缀排序中 S 的每个后缀的前缀中是否具有 T，从二分到的后缀单次比较 T 与这个后缀的前缀的大小关系，耗费 O(|T|) 的时间复杂度。
可以通过二分找到极小与极大位置。
3
两子串最长公共前缀。
Sol
记 S1 = [s_l......s_r] = (l,r)，S2 = [s_L......S_R] = (L,R)。
若询问 S1 与 S2 的最长公共前缀，问题可转化为求编号为 l 以及编号为 L 的后缀的最长公共前缀后与 \min(r-l+1,R-L+1) 取 \min 即可。
又通过 |lcp(sa_i,sa_j)| = \min(ht_{i+1},......ht_{j}) 可以计算两个后缀的前缀，解决了该问题。
4
不同子串的数目。
Sol
令 n = |S|。
考虑求出 ht 数组。
先计算总共子串共 \frac{n(n+1)}{2} 个，接着枚举每个后缀，计算其前缀是否已经被后面的后缀计算过了。
由于 ht_i = |lcp(sa_i,sa_{i-1})|，并且根据 |lcp(sa_i,sa_j)| = \min(ht_{i+1},......ht_{j}) 可知：
所以对一个后缀 $i$ 的所有前缀算重时只需要剔除后缀 $i + 1$ 中相同的前缀，即 $ht_{i + 1}$ 即可。
最后总的计算公式为：
$Sum = \frac{n(n+1)}{2} - \sum_{i=2} ^ n ht_i$。
# 5
出现至少 k 次的子串的最大长度。
# Sol
考虑一个子串出现了至少 $k$ 次，考虑后缀排序后其至少会在其中 $k$ 个后缀里面出现，并且由于已经进行了后缀排序所以会在连续的 $k$ 个后缀里面出现。
求出 $ht$ 数组后对任意一个长度为 $k$ 的区间求出区间内 $ht$ 值的最小值。这个最小值即是这 $k$ 个后缀里出现了至少 $k$ 次的子串的最大长度，枚举完所有区间求出最大的子串即可。（对于第一个区间要刨去 $ht_1$）
由于问题的形式变为滑动窗口，使用单调队列即可在 $O(n)$ 解决一个 $k$ 的询问。
# 6
是否有某字符串在文本串中至少不重叠地出现了两次。
# Sol
其实问题应该可以加强成求最长的一个在文本串中至少不重叠地出现了两次的字符串。
考虑二分这个字符串的大小，记为 $sz$。
将 $ht$ 数组（还是除去 $ht_1$）分为若干个大小都大于等于 $sz$ 的段，这样可以通过数据结构查询后缀排序后的区间最小/最大下标（即后缀的编号），然后看两个下标的距离是否大于等于 $sz$ 即可判断一个 $sz$ 是否有解。
时间复杂度 $O(n \log n)$。
# 7
求出最长回文子串。
# Sol
~~怎么了？我后缀数组 $O(n)$ 排序，rmq 用 $O(n)$ 也是总时间 $O(n)$ 的。~~
考虑一个回文串具有的性质：从中间剖开，将左边串反转后等于右边串。
记 $S$ 为原串，$S'$ 为 reverse 后的原串，特殊字符为 $b$。
构造一个 $SbS'$ 的字符串，并将其后缀排序并求出 $ht$ 数组。
枚举每个点作为奇数回文串的中间点/每个间隙为偶数回文串的中间分界后，在 $S$ 与 $S'$ 中找到对应的位置，问题转化为两个后缀的 lcp。
# 8
求以 $x$ 为开头/结尾开始计，延伸出去 $k$ 个相同子串的方案数。
eg：对于 $aaaaaa,k=2$，对于以 $1$ 开头有 $(a,a),(aa,aa),(aaa,aaa)$ 三种方案。
# Sol
考虑一种很脑洞的计数方法：枚举长度 $len$ 的作为相同子串的长度。
那么我们将每 $len$ 个点标为一个关键点，一个方案必定过了 $k$ 个关键点。
对于 $k=2$ 可以参考这篇[讲解比较清楚的博客](https://www.luogu.com.cn/blog/user42506/solution-p1117)。
对于 $k>2$，其实就是将每 $k$ 个点做考虑，是一样的。
证明的话可以拆成 $k-1$ 个 $k=2$ 的形式来看。
时间复杂度 $O(nw)$。
# 9
对于每个 $r \in[1,n]$，定义 $d(r)$ 为字符串中满足 $lcp(suf_i,suf_j) \geq r$ 的二元组 $(i,j)$ 对数（有序无序都能求）
求出所有的 $d(r)$。
# Sol
答案递增。
考虑用并查集，单调递减处理 $r$，每次在 $ht$ 数组上合并段，使得每个 $r$ 形成的段内部的值都大于等于 $r$，统计每个段的贡献即可。
注意不考虑所有 $<r$ 的 $ht_i$。
# 10
给定 $n$ 个串，求每个串之间的最长公共子串长度。
# Sol
令 $L = \sum_{i=1} ^ n |S_i|$。
提供一种 $O(Ln + L \log L)$ 的方法。
这个还是很简单的，就直接把所有串拼在一起，每个串之间间隔一个特殊字符，每扫到一个位置就直接用当前这个位置所对应的字符串 $i$ 去与之前能匹配到的所有串在后缀排序后的 $lst$ 求 $\min$。
使用 ST 表即可。
# 11
询问去重/不去重的字典序 $k$ 大子串。
# Sol
考虑枚举每一位的字符，也可以描述为从小到大枚举前缀。
滚一个后缀的前缀和，方便计算一个区间内包含了一个前缀的子串数。
显然一个前缀肯定是被一个区间 $[l,r]$ 包含的，在每次枚举前缀时即可缩放这个区间，接着用类似 Trie 树上分治走的方法即可解决该问题。
时间复杂度是 $O(n \log n |\sum|)$，应该可以在答案串为 $zzz......zzzz$ 时卡满，但是也应该没人闲到卡这个吧。
实现较为复杂，不推荐该种做法，建议下方参考 SAM 的做法，比这东西又快有简洁，不知道 OI-WIKI 是觉得这个做法哪里简单。
# SAM/广义 SAM
以下的后缀自动机都取是对 $S$ 建的。
都省略了后缀自动机带来的时间复杂度的影响。
# 1
询问 $T$ 是否是 $S$ 的子串/$T$ 与 $S$ 子串的最大匹配前缀。
# Sol
考虑 SAM 从 $st$ 开始走的路径能严格不交地包含 $S$ 所有的子串。
所以直接匹配从 $st$ 向下走就好了。
时间复杂度 $O(|T|)$。
# 2
询问不同子串数。
# Sol
与后缀数组一个套路。
由于在 parent 树上每个节点都是由父亲节点进行严格划分得到的，所以考虑容斥。每个点只计算不被父亲统计到的子串即可，即 $g(i) = len_i - len_{link_i}$。
时间复杂度 $O(|S|)$。
# 3
询问去重/不去重 K 大子串。
# Sol
去重/不去重无非就是将一个位置的 $Endpos$ 集合大小设置为 $1$ 或实际大小。
然后在后缀自动机上维护走到下一个点时会新增多少路径，这个可以先在 parent tree 上算一遍 $endpos$ 集合后搬到 DAG 上再算一遍求出路径。
然后还是像 Trie 一样分治找即可。
时空复杂度 $O(n |\sum|)$，使用链表维护可以将时间复杂度压到 $O(n)$。
# 4
字符串最小循环位移。
# Sol
这个确实就后缀数组优势大一些。
SAM 的话，就求 $S + S$ 的最小的长度为 $|S|$ 的子串就好了。
这个直接向下跑就好了。
时间复杂度 $O(|S|)$，至于排序的话个人还不是很想胡。
# 5
字符串 $T$ 在 $S$ 中出现的次数。
# Sol
处理出每个状态的 $endpos$ 集合大小，然后找到 $T$ 对应的状态即可。
时间复杂度 $O(|T|)$。
# 6
字符串 $T$ 在 $S$ 中出现的第一个位置。
# Sol
直接在 parent tree 上应该可以直接预处理子树内最小的 $endpos$ 吧？
OI-WIKI 在说什么……
然后多次查 $k$ 大的话可以离线后线段树合并。（口胡）
# 7
同问题 $6$，改为所有出现的位置。
# Sol
单次查询的话，可以找到模式串位置后暴力遍历子树，单次查询即可做到 $O(|S|)$。
多次查询就离线询问，启发式合并就好了。
# 8
这个我不是很理解它在干什么。
# 9
求 $S$ 与 $T$ 的最长公共子串。
# Sol
对 $S$ 建立后缀自动机，对 $T$ 的每个前缀匹配最长后缀。
我们假设当前状态为 $p$，当前匹配的长为 $l$。
分两种情况进行 $T_i$ 的加入：
- 若 $p$ 有向 $T_i$ 的转移，让 $l + 1$ 后由 $p$ 通过该边转入下一个状态。
- 若 $p$ 无向 $T_i$ 的转移，向 $link_p$ 移动，并将 $l$ 赋值为 $len_{link_p}$。
情况一的正确性比较显然。
对于情况二，由于能到达 $p$ 状态中的任何一个子串，并且此时所有该状态下（即一个 $endpos$ 等价类的子串）无法接着转移，$link_p$ 中的任何一个子串都能到达，所以跳到 $link_p$ 去，并且将 $l$ 更新为状态里面最大的子串。
显然这么做 $l$ 只会在一次加入时至多自增 $1$，而每次至少减少 $1$，经典势能分析复杂度。
时间复杂度 $O(|T|)$。
# 10
求多个串的本质不同子串个数。
# Sol
直接广义后缀自动机建出来后变成了问题 **2**。
# 11
求两个串各取一个子串出来相同的情况，考虑/不考虑位置不同。
# Sol
不考虑位置不同就看一个状态下是否两个子串的 $endpos$ 集合大小是否都不为 $0$，是的话贡献 $len_i - len_{link_{i}}$ 否则贡献 $0$。
考虑位置相同就把 $endpos$ 集合算上后乘一下。
# 12
一个文本串 $S$，多个模式串 $T$。
多次询问一个文本串 $S$ 的子串 $[S_l,...S_r]$ 在 $[T_L,......T_R]$ 中能匹配最多的一个模式串。
# Sol
其实还是比较裸的了。
单串都会做，多串就是扩展到广义 SAM 上，线段树合并维护多串的 endpos 即可。
时间复杂度 $O(|S| \log m)$。
# 13
对一个叶子个数为 $K$ 的无根树计算本质不同路径。
# Sol
提供一种 $O(K |S|)$ 的做法。
首先有一个我都不知道的结论：无根树的任意路径必将在一个叶子节点为根时成为一条一路向下的链。
我们将每个叶子节点作为根时的 Trie 树插入广义 SAM 中，由于计算本质不同的子串，所以多重插几个子串没有任何关系。
然后就可以直接算了。
~~所以树上后缀排序也可以解决该问题。~~
# 14
给定一个文本串，询问多个模式串循环同构在文本串中出现次数之和。
# Sol
~~这哪里要广义 SAM 了。~~
考虑对于文本串直接建立 SAM，求出 endpos 集合大小，对于循环同构用 hash 去个重，每一次删除首字符就相当于把当前的 len 减去 $1$，如果 $len$ 已经不能在 $i$ 这个状态上呆下去了就跳到 $link_i$ 上去，然后就在每个状态下加一下 endpos 集合大小，做完了。
# 15
广义 SAM 离线构造 trie 树伪代码：
```cpp
int n,m,head[Len],cnt,pos[Len],ff[Len];
char cc[Len];
struct Node
{
int next,to;
int ch;
}edge[Len << 1];
void add(int from,int to)
{
edge[++ cnt].to = to;
edge[cnt].next = head[from];
edge[cnt].ch = cc[to] - 'a';
head[from] = cnt;
}
void dfs(int x,int f)
{
pos[x] = At.ins(cc[x] - 'a' , pos[f]);
for(int e = head[x] ; e ; e = edge[e].next)
{
int to = edge[e].to;
if(to == f) continue;
dfs(to , x);
}
}
```