后缀自动机的一些小技巧

19.3.31UPD

其实是一些很基础很入门很傻逼的东西，就不加密了

常见简单思想

拓扑序dp

SAM的拓扑序有一个性质，如果有一条转移边 $u \rightarrow v$则一定有 $|\mathrm{maxlen}_u| < |\mathrm{maxlen}_v|$；如果 $\mathrm{fa}_v = u$也有 $|\mathrm{maxlen}_u| < |\mathrm{maxlen}_v|$

因此按照maxlen从小到大排序就能实现拓扑序的过程

此外，转移边上走是拓扑序正序；跳fa是拓扑序逆序

求right集合

在所有前缀$i$所在状态的right集合中加入$i$

在parent树上线段树合并

利用parent树

由于是树形结构，就可以进行一些树上的操作

树上倍增、LCT、点分治等

建后缀树

把原串倒着建SAM所形成的parent树即为后缀树

两个子串的lcp长度就是后缀树上两个节点的lca的maxlen(注意不是深度！！！)

也可以这么理解，对于SAM上两个结点，它们往parent树向上跳的过程就是不断缩后缀的过程，那么parent树的lca就是它们的最长公共后缀。于是把原串反着建就变成了lcp

经典应用

最基础

最长可重叠k重复子串

给出一个字符串$S$，找一个子串，使得至少出现$k$次，可以重叠，求最长子串长度

right集合大于等于的那些节点的最大的maxlen

最长不可重叠重复子串

给出一个字符串$S$，找一个子串，使得至少出现两次，不能重叠，求最长子串长度

不光要使得right集合大于等于2，还需要考虑最靠右的那个位置和最靠左的那个位置之间的距离

循环同构的最小表示法

设 $S$ 为一字符串，$S_i,(i \in [1, |S|)$表示将 $S$ 的前 $i$ 位剪切并拼接在 $S$ 的最后得到的字符串，所有 $S_i$中字典序最小的一个，称为 $S$ 循环同构的最小表示

给出一个字符串$S$，求它的最小表示

直接把$S$倍长建SAM，从根开始贪心走最小的转移边，走$|S|$步得到的字符串即为答案

本质不同子串个数

给出一个字符串$S$ ，计算本质不同子串的个数。

所有状态包含的子串总数

$\sum_i maxlen[i] - maxlen[fa[i]]$

稍微有点难度

任意子串的出现次数

给字符串

给出一个字符串$S$ ，多次询问一个模式串$T$ ，求$T$在字符串$S$中作为子串出现了多少次

在这里提到了，一个子串的出现次数就是它所在状态right集合的大小，且只有传统节点才会有贡献

先parent树上子树求和，然后每次读进来一个串时就把它扔到SAM暴力匹配，答案就是最后走到的节点的right集合大小，复杂度$O(\sum T)$

• 加强：

  求$T$在$S$中的一个区间$[l_i, r_i]$中出现多少次

  线段树合并求right集合，查区间和

给区间

给出一个字符串$S$ ，多次询问给出$[l, r]$，求$S$的子串$[l, r]$在$S$中出现了多少次

与上面做法类似，但是就不能暴力匹配了。因为复杂度可能达到

考虑类似于「TJOI / HEOI2016」字符串的做法，从前缀$r$在SAM中所表示的状态开始，倍增跳parent树，找到满足$\mathrm{minlen}\le r - l + 1 \le \mathrm{maxlen}$的祖先，求那个节点的right集合大小即可

第k小子串

本质不同第k小

给出一个字符串$S$，求它子串中本质不同的第$k$小子串

按拓扑序（或者在转移的DAG树上）求出以每个状态开头的本质不同子串个数（直接dp即可）

然后按照主席树求第$k$小的方法，贪心枚举每一位，这个节点的某个儿子的大小$>k$，说明要找的串在这个儿子里；否则$k$减去节点大小，继续找

注意，这里求出来的大小和right集合大小是不一样的。。。right集合大小是在原串中的出现次数，这个是以它开头的子串个数

所有子串第k小

给出一个字符串$S$，求它所有子串中第$k$小子串

上面的做法算上right集合的大小即可

两个字符串的最长公共子串

给出两个字符串$S,T$，求它们的最长公共子串

这里和这道题也讲过了，建出$S$的SAM，把$T$的所有前缀扔进去匹配，求个最大值

多个字符串的最长公共子串

给出个字符串，求它们的最长公共子串

• 直接建广义SAM，不过这个东西我暂时没太理解。。。
• 对第一个字符串建SAM，把后面的串扔上去匹配，匹配的时候记录一下这个状态对于当前这个串的最长公共子串，然后每次对所有状态取个min即可

动态求子串出现次数

给出一个初始字符串，每次往后添加一个字符或者询问一个子串在该字符串中出现次数

动态维护right集合大小，可以用LCT维护。如果不强制在线还可以直接树剖

广义后缀自动机

版本一

考虑建立多个串的 SAM ，构造时一个一个串插入，插入完一个串后将 last 设为 root 再重新开始

版本二

考虑建立 Trie 的 SAM 。插入完 Trie 节点 $x$的时候记录一下 tmp = last ，然后插入完$x$ 的某个子树后，再将 last 赋为 tmp ，再插入另一个子树。

版本三

通过离线Bfs这棵Trie树构造，与上面的做法类似，但是似乎复杂度有保证

---

前两种方法复杂度好像不太稳定，可以卡。这东西我还不是太理解，有点玄学。。。