后缀自动机
今天听了ZR 敦爷的课加上以前和zbww讨论了一下，感觉对后缀自动机和后缀数据结构有了船新认识！QWQ
后缀自动机大概分成了下面三部分：
-$n^2$后缀树的构建
- 后缀自动机构建及基础应用
- 缩边并且得到$O(n)$个点的真正的后缀自动机！
后缀树
其实后缀树才是本质的后缀数据结构。
First step 后缀树构建
把单词的后缀插入一棵 Trie 就可以得到后缀树，节点数是$O(n^2)$的。注意，到现在我们还是考虑$O(n^2)$的后缀树。
后缀树上的一个节点其实就对应了一个子串。
其实后缀数组只是后缀树的 DFS 序。
后缀树上点$x$是$y$的祖先，那么$x$明显是$y$的前缀。
一个串$x$出现次数就是它是几个后缀的也就是子树中有多少个后缀点。
显然
一个串在$L$处出现，等价于它是$suf[L]$的前缀，等价于它是$key[L]$的祖先。
显然
那么怎么求$LCP( suf(x),suf(y) )$
前缀关系就是它们的祖先所以就是找$LCA(key(x),key(y))$
本质不同的子串个数
其实就是后缀树的节点个数
最长出现超过$K$次的子串
我们只需要计算每个节点对应出现次数。前面说过了。可以 dfs 一次算出
最长不重叠出现超过$K$次
类似后缀数组二分 L 用$H_i \leq L$割开来算。
也就是说，换在后缀树上，如果$len[x] \leq L$我们就dfs这个子树。
否则如果$len[x] \geq L$我们把子树那的$key$点取出来，排序，然后从左往右能选就选。
求 LCS
把$S , T$拼一起建后缀树。
求一个子串，它在$S$中出现，且在$T$中出现。
也就是说它是$S$某后缀前缀，也是$T$某后缀前缀。
也就是说子树内有$S$的$key$点也有$T$的$key$点。
求第$k$小的子串
按照出边 dfs 下去就好了。
Second step 后缀自动机构建及基础应用
注意，到现在为止还是$O(n^2)$的后缀树！
首先我们拿出一棵后缀树，并且定义：
一个点的$len$表示这个点代表的子串的长度
一个点的父亲（$par[x]$）表示这个点在后缀树上的父亲。
到现在还是后缀树，后缀自动机和后缀树差的其实就是一个 “转移” 数组
-$son[x][c]$在这里后缀树从$x$这个节点代表的子串是往前加字符得到的节点！往后加字符其实构造出来的是前缀树，为了和前面后缀树的拼接我们暂时用$son[x][c]$表示往前加字符的！
现在我们就有了一个基本的后缀自动机。
构建考虑增量法
我们现在有$S$的后缀自动机，考虑往前加入一个字符，怎么整出$cS$的后缀自动机？
步骤大概是：给$cS$这个串建立一个节点，然后给它找到父亲/祖先们，最后整出它的转移。
首先，它的祖先肯定是$cS[1…t]$，这个祖先也有可能不存在，也就是说整个字符串没有$c$这个字母。
我们要先找这个最近的已经存在的祖先（或者是根），再把剩下的祖先建立出来。
首先$cS[1…t]$肯定是$son[S[1…t]][c]$。
如何找到$S[1\dots t]$?很显然的是，$S[1…t]$是$S$的祖先，所以我们可以从$S$向上跳，直到找到$son[x][c]$有值。
然后我们就从$cS[1…t]$往上补全，同时把中间的部分补全，这样我们就构造好了父亲。
然后考虑怎么构造$son$,这些新加进去的点肯定是没有$son$的，如果它加字符还可以连向其他的点，那么它一定是出现过的，即$cS[1…d]$是$S$的一个子串。
考虑什么点的$son$会连向它？其实就是$S$一步步跳到$S[1…t]$中途的点可以通过添加$c$一一对应到这些点。
如果这样的祖先不存在，说明没有$c$出现过，直接从后缀根开始构造就好了。
总结下来一句话，爬链，创链，连链。
Third step 缩边并且得到$O(n)$个点的真正的后缀自动机！
到现在我们的后缀树还是$O(n^2)$节点的，显然是成不了大事的。
这个树叶子数量只有$O(n)$的（后缀数量），也就是说它看起来是非常臃肿。
我们考虑这样的一个事实：如果一个树不存在 只有一个儿子的点 那么点数和叶子数同阶。（画个每个点都至少两个儿子的树就发现是非常显然的了，每次一个点至少合并了两个部分叶子，至少就是$O(2n)$个点）
那么也就是说如果我们可以把只有一个儿子的点压缩了，这就是个线性的树了！
但是我们希望压缩后不会损失信息，所以我们希望 ...- a - a - a -... 这样的树压缩后直接变成了 ... - aaa - ...，最终剩下的点保存的不再是一个串，而可能是几个串。
我们称最后留下来的点叫做关键点。当然叶子还是留着的，我们称之为后缀点。
到这里，发现其实直接对$sa$建虚树和我们最后希望压缩结束的树，本质上是一样的。
但是剩下的关键点，它代表的不再只是一个串了！
所以现在，原来的定义不太适用了，有了新的定义：
定义一个点代表的串的集合是$Z(x)$
同时，$len(x)$的定义也变化了，定义现在是$Z(x)$里面最长串的长度。
然后，定义$fail(x)$就是一个点往祖先爬的第一个关键点，我们也有$|Z(x)| = len(x) - len(fail(x))$。
如何保证一个点被压缩，它的信息仍然留存在关键点上？
现在我们需要证明原树上如果$T$是被压缩的点，那么$son[c][T]$也是被压缩的点
-$cT$是后缀点，那么$T$也是后缀点，矛盾
-$cT$有2个儿子，$cT$也会有两个儿子，矛盾但是如果$x$是一个关键点，$son[x][c]$却可能是被压缩点。
这种情况我们让$son[x][c]$连到它被压缩到的点中。
于是，我们相当于更改了$son$的定义，对于$Y\in Z(x)$，$cY \in Z(son_{new}[x][c])$
这样的话，我们就有了一个无损压缩，既压缩了点又没丢失信息。
怎么构造呢？
回忆一下，刚刚我们构造$n^2$后缀自动机，我们的操作是 爬链，加链，连链（改$son$）
我们能不能更改这个过程，使得构造出来的节点数是$O(n)$的呢？
一样的，假设我们已经对$S$构造出了$O(n)$节点的后缀自动机，加入字符$c$得到$cS$，从$S$所在节点开始爬链。
假设为$cS$新建的点是$P$。
我们假设爬链得到的点是$Q$，$E = son[Q][c]$，也就是说最长的$cS[1…t]$在$E$上 。
但是它可能实际上想链接的是$E$中的某个串在未压缩时所对应的某个子串。根据$fail$的定义是不能把$fail[P]$直接连向$E$的。
如果$len[E] = len[Q] + 1$，想要连接的就是$E$，因为$cS[1\dots t]$就是$E$所对应的最长串长度+1，直接$son[Q][c] = E$就好了，否则如果$len[E] > len[Q] + 1$， 我们需要连接的是一个$Z(E)$中的某个串，方法就是把这个串分裂出来。
假设$Q$想要连接到的串（$Z(E)$中的一个串 ）以及它的 / 存在于$E$的 / 前缀都拿出来建立一个点叫做$k$。现在$E$就相当于被切开了。
于是，$E$的父亲就变成了$k$。
所以把$k$的父亲指向$E$原来的父亲，并且把$E$和$P$的父亲都设置为$k$。
现在爬链不变，加链就变成了拆点，分裂出一个点，从加链变成了加点。
最后还需要更新一下$Q$祖先（包括$Q$）往$c$的转移，即如果有往$c$的转移并且转移向$E$，就把它改成$k$就好了。
基本操作
其实往前加字符和往后加效果是一样的，后面我们就考虑往后加字符了，这样后缀树就变成了前缀树，理解应用的时候更轻松。
再回头看一下$go$数组，可以发现它拥有一个有用的性质：
- 如果$S \in Z(x)$那么$Sc \in Z(go[x][c])$
也就是说，要找到了$T$的节点，其实就是从根出发，按照$T$的字符走$go[x][c]$就好了。
本质不同的子串个数
后缀树的节点个数，就是每个点的$len[x] - len[fail[x]]$的和
一个串的出现次数
其实就是找$key[L]$的祖先，这些祖先含有$[len[fail[x]] +1, len[x]]$个本质不同的子串
最小循环串
找$SS$长为$|S|$的最小子串。
从根开始走了$k$步必然就是一个长度为$k$的子串。
既然找最小，每次走最小的边，走$|S|$次。
如果走到了尽头，那么我们必然走到了一个后缀，但是一个后缀在$SS$中，如果长度不超过$|S|$那么必然可以继续走，所以如果真的走到了死胡同那么当前的大小肯定大于了$|S|$不符合题设。
-$S[L…R]$的定位
$S$必然是$key[R]$的祖先，直接倍增就好了。
求长度为$k$的字典序最小的子串
一个 Trivial 的做法是，走$k$步，每次走最小，这样很容易走到死胡同。
可以求一个$f[i]$表示从$i$开始最长可以走多少步。就是求一个类似拓扑图深度的东西。
求$S,T$有多少对子串相等
$\sum_{x} (cnt_{S,x})(cnt_{T,y})$
可以把这两个串拼起来然后搞后缀树，答案就是对于某个点它子树里面$S$的后缀个数和$T$的后缀个数。
$\sum (len[x]-len[fail[x]]) S(x) T(x)$，$S(x)$表示$x$子树中$S$后缀个数，$T$同理。
本质不同乘的是$[S(x)>0]$
然后 LCS
还是拼起来，搞后缀树，
最长至少出现了 $k$次的子串
对于$x$，求出$x$出现了$S(x)$次，如果$\geq k$就统计就好了
求第$K$小的子串，要求$O(Qn)$
从小到达遍历子串，$F[x]$表示从$x$出发可以走到多少个不同的子串。
设$f(i)$为长度为$f(i)$的子串的出现次数最大值，求 所有$f$，要求线性。
出现次数可以方便地在后缀树上 dp
它可以让长度为$len[fail[x]] + 1 … len[i]$做贡献。
其实可以看成对前缀取max，因为没有
毒瘤：每次往后加$a$，求$T$在$S$出现次数
离线很好做，就是这个题的弱化版 DQS的trie
加一个叶子，把一条边裂开
链加，加叶子，裂边，LCT
给定$n$个字符串，求有几个字符串至少是$K$个串的子串
$\sum |S| \leq 10^5,n,k \leq 100$
对于一个点，我们需要求出它的子树中有无$S_i$的后缀。
这个东西我以前的做法复杂度不可证明，现在老师给了种复杂度正确的做法，
为了保证每个点被一个串抓到，可以这样做，对于每个点到根+1，按照dfs序排序后将两两相邻LCA到根-1。
这样类似虚树地做，假设一个点有$k$个关键点儿子，它会被加$k - (k-1)$次。