后缀自动机 Suffix Automation
推荐博客 link
子串问题可以考虑 (trie)
但是如果要维护不同子串个数类似的问题的话，(trie) 的 (DAG) 的量到了 (O(n^2))
那么后缀自动机作为压缩的 (trie) 就应运而生了，主要是合并了大量没用的节点
首先是一个子串的 ({endpos}) 表示当前子串的在大串里面结尾下标的集合
每个 (endpos) 会对应若干个子串，这些子串长度必然连续
如果在这些子串里面最长的前面加入两个不同的字符，可以把当前集合分成两个没有交集的集合（可能有元素没有被分到这两个集合里面）
那么可以得到 ({endpos}) 的数量级是 (O(n)) 的，像线段树式的分割方法可以得到最大的数目
如果考虑把母集作为分割出来小集合的父亲，就可以得到一个树，这里是 (Parent Tree)
这里有一个性质，设 (mx(x)) 为当前 ({x}) 的最长的字符串的长度，(mn(x)) 为最短的字符串的长度，那么有 (mx(fa_x)+1=mn(x))
证明就是子集合是父亲加字符，所以就好理解了
针对 (endpos) 的定义和性质可以得到以下的性质：
((1) SAM) 的每个点代表的是一个 (endpos)，从源点通过加边到达这个点的字符串要保证它的 (endpos) 是这个集合
但是可能并不会把这个 (endpos) 到底是几显式地表示出来
((2)) 到达 (fa_x) 的任意字符串是到达 (x) 的后缀
因为 ${x o endpos}subsetneq { fa_x o endpos} $，这里和平常的字符串维护不太一样
颠覆了一点认知，但是仔细思考上面说的 (endpos) 的性质还是成立的
那么后缀自动机的构建就是使它满足这个条件
首先每次新加入一个字符得到的字符串所有的后缀的 (endpos) 都会改变
那么遍历所有原串的后缀，如果没有 (x) 的出边，就连上（这样保证了 (sam) 有维护子串个数的功能）
如果出现有且满足 (len_p=len_{tmp}+1) ，那么按照 (endpos) 来理解，就直接把 (fa[np]) 设为 (q) 就行了
如果出现了 (q) 但是不满足 (len_p=len_{tmp}+1) ，那么需要新建一个节点 (clone)
也就是分割 (endpos)
然后把 (q) 的信息给到 (clone) 接着把所有的前面满足相应的 (endpos) 指向 (clone)
那么大概就建完了
inline void extend(int x){
int tmp=las,np=las=++tot; len[np]=len[tmp]+1;
while(tmp&&!ch[tmp][x]) ch[tmp][x]=np,tmp=fa[tmp];
if(!tmp) return fa[np]=1,void();
int q=ch[tmp][x];
if(len[q]==len[tmp]+1) return fa[np]=q,void();
int clone=++tot; fa[clone]=fa[q]; fa[q]=fa[np]=clone; copy(clone,q);
len[clone]=len[tmp]+1;
while(tmp&&ch[tmp][x]==q) ch[tmp][x]=clone,tmp=fa[tmp];
return ;
}
应用
判断子串：和 (AC) 自动机类似
求在原串所有子串中（相同的算或者不算一个）字典序第 (i) 大
每个串出现的次数等价于建出来后缀树之后对应的 (endpos) 对应的点的子树的点全和
(dp) 得到后缀树上面的子树点权值，然后考虑从这个字母出去的子串有几个的时候要考虑在 (DAG) 上面处理
输出考虑树上二分即可
求本质不同的子串个数
考虑到 (sam) 上根节点到任意一个点都是一个子串，且其本身是个 (Dag)
所以拓扑 (dp) 一下就好了
如果在线的话，那就考虑每个点的贡献吧：(max_i-min_i+1) 即 (max_i-max[fa[i]])
两串 (LCP) :
其实就是后缀树上点的 (lca) 的 (len)（然后“差异”那个题就可以考虑每条边的长度是 (len_i-len[fa[i]]) 然后贡献法一下了）
关于后缀树：
这个比较就是每个点的父亲向点建边，建成了一棵树，就是后缀树
最小表示法：
这个比较简单了，把原串复制一遍，然后直接在后缀自动机上面跑，能往小的点上跑，就跑，没有后继节点就跳 (fail)
求最长公共子串的长度：
用其中一个字符串建后缀自动机，然后把其它的子串放在上面匹配
记录下来每个点匹配的最长长度，然后在每个点上面取记录下来 (max) 的 (min) 吧
最后的答案就是所有点 (min) 的 (max)
（很绕，但是很好理解）
相关复杂度:
((1)) 建后缀自动机的复杂度和后缀自动机的点数是 (O(n)) 的
((2)) 后缀树和 (parent) 树的节点数量级是 (O(n)) 的
((3)) 遍历后缀自动机对应的 (DAG) 是 (O(n^2)) 的
关于广义 (sam)
支持了多串匹配的功能，现在会了那个正经的特判在线写法
一个例题是 $ [USACO17DEC]Standing Out from the Herd P $
考虑按照 有个省选题的做法可以存 (sz[id][x]) ，但是空间会炸，应该用大量stl也是能写的
其实发现只用维护每个点是不是被经过了两次
所以标记即可
或者是 (SNOI2020) 字符串
考虑修改两个字符串的代价 (k-dep[lca])
那就搞出来广义 (SAM)，把所有的子串在对应节点上打上标记
然后建后缀树，现在问题转化成了：树上有一些点，求让这些点两两匹配后每对 (lca) 的深度之和最大
贪心发现每两个在它最先能匹配的 (lca) 匹配会优，那么甚至都可以不用 (dp)
记得判断 (len[x]>k) 的时候直接赋成 (k) 就完事了