后缀自动机大型总结
终于填上这个坑了woc
怎么实现的以及原理不想写了
总结一下套路和性质？
基本问题1、 求多个串的\(\text{LCS}\)。
有两个做法，只会一种，就是对第一个串建\(\text{SAM}\)，剩下的串在\(\text{SAM}\)上跑，在每个节点记录一下当前串的最长匹配长度，以及所有串的最短匹配长度。最长匹配长度要对子树取\(\max\)因为能匹配一个点的孩子肯定能匹配该点。
2、 统计某个子串的出现次数。
这个可以放在\(\text{SAM}\)上跑匹配，假设匹配到了点 \(x\)，那就在\(\text{parent}\)树上一直跳\(\text{father}\)并且还要满足当前点的\(\text{len}\)要大于等于该子串的长度。最后跳到的点在\(\text{parent}\)树上的\(\text{size}\)就是答案。
3、 求一个字符串的最小表示。
可以把串倍长一遍接在后面，然后对新串建\(\text{SAM}\)，在上面每个点都选一个字典序最小的出边跑过去就好了，这样肯定能找到长度为原长的某个子串。
4、 求排名第 \(k\) 小的子串（本质相同算一种/多种）。
首先记录 \(f[i]\) 表示从自动机上点 \(i\) 开始，有多少个不同的子串。\(f[i]\) 的初值是 \(size[i]\)，如果本质相同算一种，那么 \(size[i]=1\)，否则 \(size[i]\) 为 \(\text{parent}\)树上点 \(i\) 的子树\(\text{size}\)。为什么要这么设初值？这两种问题的区别就是，可以在每个点“结束”多少次，或者说从自动机上的点开始走，那可以在原串的几个位置走。然后在\(\text{DAG}\)上\(\text{DP}\)出来所有点的 \(f\) 值。接着从小到大类似平衡树找第 \(k\) 大那样找就好了。注意每次走过一条边都可以直接在当前点结束一个子串 暴毙，所以每走过一个点都需要减去当前点的 \(size\)，表示可以在这里就产生一个子串。
5、 给定一个主串和一个询问串，多组询问，每次求询问串的 \([l,r]\) 能否在主串中匹配。
可以先把整个询问串拿上主串的\(\text{SAM}\)跑一遍匹配，在第 \(i\) 位记录 \(mx[i]\) 表示询问串匹配的右端点是 \(i\) 时，最长能匹配多长。根据单调性，如果可以匹配 \([i-mx[i]+1,i]\)，那一定可以匹配 \([i-mx[i]+2,i]\)。
6、 给定一个主串和一个询问串，多组询问，每次求询问串的 \([l,r]\) 在主串中出现了多少次。
还是先把整个询问串拿到主串的\(\text{SAM}\)上跑一遍，记录 \(mx[i]\) 的同时记录 \(pos[i]\) 表示询问串匹配的右端点是 \(i\) 时，在自动机上的位置。对于询问 \([l,r]\)，如果 \(mx[r]<r-l+1\)，答案为 \(0\)。否则需要在\(\text{parent}\)树上倍增找到最顶端的 \(i\) 满足 \(len[i]\ge r-l+1\)。此时的 \(sze[i]\) 就是答案。
7、给定一个字符串，求该字符串所有仅出现了一次的子串
先建出\(\text{SAM}\)，很明显只出现了一次的子串一定是\(\text{parent}\)树上的叶子节点，他们的\(\text{endpos}\)集合大小必定为 \(1\)。记录 \(end[i]\) 表示自动机上点 \(i\) 对应的子串的任意一个结束位置，那么对于叶子节点 \(i\)，它对应的子串的出现位置就是 \([end[i]-len[i]+1,end[i]]\)。
8、给定字符串，多组询问。每次给定该字符串的若干后缀，求两两\(\text{LCP}\)长度。\(\sum t\leq 3\cdot 10^6\)
首先两个后缀的\(\text{LCP}\)长度就是它们在反串的\(\text{parent}\)树上\(\text{LCA}\)的 \(len\) 值。那多个后缀两两\(\text{LCP}\)长度就可以通过树形\(\text{DP}\)来求。又因为 \(\sum t\leq 3\cdot 10^6\)，所以可以建虚树，在虚树上\(\text{DP}\)就行了。
9、给定一个主串和多个询问串，求询问串的每个前缀在主串的\([l,r]\)区间内出现了多少次。\(\sum t\leq 3\cdot 10^6\)
对主串建出\(\text{SAM}\)后利用线段树合并维护每个点的\(\text{endpos}\)集合。同时拿询问串在主串上面匹配，若匹配到了询问串的第 \(i\) 个字符，当前在自动机上的点 \(j\)，那么在点 \(j\) 的线段树上询问一下在 \([l,r]\) 内的值即可。
10、给定一个主串和多个询问串，求询问串所有本质不同的循环同构串中，每个串在主串的出现次数