后缀自动机上存储着一个串的所有后缀，由于所有子串都能通过添加字符变为后缀，所以所有子串也都存储在后缀自动机中
后缀自动机之所以能压缩状态，是因为把所有 \(endpos\) 集合相同的串归为一个状态
定义 \(endpos(S)\) 指串 \(S\) 在母串中所有出现时结尾位置的集合，以 \(abaa\) 这个串为例：
\(a:1,3,4\)
\(ab,b:2\)
\(aba,ba:3\)
\(abaa,baa,aa:4\)
对于每一类 \(endpos\) 的字符串，都归入一个节点
\(SAM\) 的 \(fail\) 树上的父亲，是包含这个节点 \(endpos\) 集合的最小集合
有这样的性质：所有节点儿子的集合没有交集
对于一个 \(endpos\) 集合，如果给出一个长度 \(len\)，那么就可以唯一确定出一个子串
而对于每个集合长度 \(len\) 都有一定的限制，设为 \(minlen,maxlen\)
有这样的性质：\(minlen(p)=maxlen(fa(p))+1\)
而 \(SAM\) 本质上是一个 \(DAG\)，有向边代表字符的转移
有这样的性质：\(endpos(son[p][w])\subseteq endpos(fa[p])\)
利用以上性质可以证明 \(SAM\) 的点数与边数规模都为 \(O(n)\)
对于自动机的构建，目前来看似乎需要改动板子的情形不多，大部分情况直接理解性默写即可
void insert(int w){
int p=last,np=last=++tot;
siz[tot]=1;len[np]=len[p]+1;
for(;p&&!son[p][w];p=fa[p])son[p][w]=np;
if(!p)fa[np]=1;
else{
int q=son[p][w];
if(len[q]==len[p]+1)fa[np]=q;
else{
int nq=++tot;
fa[nq]=fa[q];for(int i=0;i<26;i++)son[nq][i]=son[q][i];
fa[q]=fa[np]=nq;len[nq]=len[p]+1;
for(;p&&son[p][w]==q;p=fa[p])son[p][w]=nq;
}
}
return ;
}
首先 \(np\) 是代表最后一个后缀的节点，整个过程一个主要目的是为了给其找父亲
顺着 \(endpos\) 是最后一个点的链往上爬直到有 \(w\) 这个儿子
如果没有，直接认 \(1\) 为儿子，结束
至于另外的情况如果不满足长度条件会产生的影响，目前还没有看懂，总之应该把 \(q\) 分裂成两个节点
首先根据本质后缀自动机上保存了这个串中的所有子串，并且每个节点上的子串各不相同
自动机相当于一张 \(DAG\)，从起点出发到任意一点结束走过的一条路径唯一对应了一个本质不同的子串
那么考虑 \(DAG\) 上的 \(dp\)，\(f[u]=1+\sum f[son]\)，注意减去空串的 \(1\)
另一种理解方式是对于每个 \(endpos\) 表示了一类子串
一个节点保存的是 \([minlen,maxlen]\) 的子串
而 \(minlen=len_{fa}+1\)
一个子串出现的个数就是当前节点保存的 \(endpos\) 集合的大小
那么集合大小可以由 \(parent\) 树上的子节点信息得来
即 \(siz[u]=\sum siz[son]\)
由于建出真实的图比较慢，可以按照 \(len\) 排序而得出父子关系，由于其小于 \(n\)，可以进行基数排序
每次增加一个字符的时候动态维护自动机上的答案
为 \(len[np]-len[fa[np]]\)
一个子串相当于从起点出发的一条路径
那么考虑 \(dp\) 出走当前节点的所有出边将会产生有多少个子串
那么直接图上 \(dp\) \(f[u]=\sum f[son]\) 即可
考虑两个串的最长公共子串应该怎样求
可以类比 \(AC\) 自动机，它的失配指针相当于指向最长公共后缀，而后缀自动机则保存了所有子串，所以是指向最长公共子串
类似与 \(AC\) 自动机，用一个串在另一个串的 \(SAM\) 上跑，若失配则条父亲，跑出来就是当前结尾的最长公共子串
如果要处理多个子串，那么把剩余的都在第一个上跑一边，对于每个位置分别取 \(min\) 即可
仍然是匹配的模式，考虑循环同构的处理方法
相当于长度扩展一倍，每次要求长度小于 \(len\)
由于本质不同的只算一次，那么后缀自动机上的每个节点打时间戳去重即可
这次多了区间的限制
考虑还是跑出长度 \(f[i]\)，那么对于区间 \([l,r]\) 相当于是查询 \(max\{min(f[i],i-l+1)\}\)
发现内层多了个 \(min\) 不好处理，由于 \(f[i]\) 每次加一具有单调性，那么可以先二分答案，使得每一个都不受限制，然后用 \(ST\) 表查询区间最大值
考虑没有区间限制的暴力做法：对 \(S\) 的 \(SAM\) 跑 \(T\) 进行匹配，跑到第一个没有匹配项的地方找到比 \(T\) 大的转移，如果都能匹配上，那么往回退，直到有一个满足条件的
现在有了区间的限制，如果能判断后缀自动机上的这个节点的 \(endpos\) 集合中有没有当前区间内的点就可以正常做了，那么直接在 \(parent\) 树上线段树合并维护 \(endpos\) 集合即可