# 〇、关于后缀自动鸡的一些~~牢骚~~废话和引入
本文同步发表于蒟蒻的[博客园博客](https://www.cnblogs.com/Arextre/p/14193525.html).
它取名叫后缀自动鸡，但是实际上在一个自动鸡出炉之后好像和后缀基本上没什么关系，按照 $\text{JZM}$ 大佬的话，叫 “子串自动鸡” 可能更恰当.
只不过，它取名叫后缀自动鸡，原因是之一可能是在原本的串 $S$ 后面插入新字符 $c$ 时，将 $S$ 的许多后缀遍历了一遍，因而得名 “后缀自动鸡”.
但是实际上，它在建成之后，自动鸡中似乎并没有彰显 “后缀” 的东西，而更像是把串 $S$ 的所有子串放到一个时空复杂度都很优秀的 $DAG$ 中.
哦，还有句话，后缀自动鸡的简称 $\text{SAM/Suffix Automaton}$，而不是 $\text{SAC/Suffix Autochiken}$. ~~但是这个错别字挺有趣的~~
# 壹、一些新概念~~英语~~
在进行正式说明前，我们有一些新概念需要理清.
## 一、终止节点等价类（$\text{endpos}/\text{right}$ 等价类）
首先，对于串 $S$ 中的每个**子串** $s_i$，我们将其出现的地方全部找出来，然后将这些出现的地方的尾端放到同一个类里面，然后给这个类取一个名字，叫终止节点集合，或者 $\text{endpos}$ 集合（在某些文章中称为 $\text{right}$ 集合），举个栗子，有这样的串：
$$
\tt abaabab
$$
我们有一个子串 $s_i=\tt aba$，发现有：
$$
s_i=S[1..3]=S[4..6]
$$
那么，$\text{endpos}_i$ 集合就是 $\{3,6\}$.
继续，现在我们每个**不同的子串**都有一个 $\text{endpos}$ 集合(显然相同的子串没啥用)，对于这些不同的子串，我们**将 $\text{endpos}$ 集合相同的子串再放到一个集合中，叫做 $\text{endpos}$ 等价类**，将这个等价类用 $\text{endpos}$ 集合中的元素进行代替.
那么，在这个例子中，有这些等价类（无特定顺序）：
$$
\begin{aligned}
&\text{endpos=}[1,n]\cap \mathcal Z,\text{string class=}\emptyset \\
&\text{endpos={1,3,4,6}},\text{string class=}\{\tt a\} \\
&\text{endpos={2,5,7}},\text{string class=}\{\tt b,ab\} \\
&\text{endpos={3,6}},\text{string class=}\{\tt ba,aba\} \\
&\text{endpos={4}},\text{string class=}\{\tt aa\} \\
&\text{endpos={7}},\text{string class=}\{\tt bab,abab,aabab,baabab,abaabab\} \\
\end{aligned}
$$
可以看到，有一些 $\text{endpos}$ 集合相同的串被归为了同一个类.
下文中，我们将用 **类** 代替 $\text{endpos}$ 等价类（能少一点就少一点）.
## 二、自动鸡
有一个叫做 $AC$ 自动鸡的东西 ~~但是不是拿来自动过题的~~，它也叫 “自动鸡”，但是到底什么是 "自动鸡" 呢？
我们认为一个东西是 "自动鸡"，有一些基本概念：
- 这里的自动鸡其实是有限状态自动鸡($\text{FSM}$)；
- 自动鸡不是 算法/数据结构，只是一种**数学模型**，对于同一个问题可能有很多只鸡，但是不是所有的鸡都满足我们解决问题时的资源消耗（比如时间和空间）；
同时，一只鸡由这几个部分组成（虽然下文不会用到）：
1. 字符集 $\Sigma$，表示这只鸡只能输入这些字符；
2. 状态集合 $Q$，即在自动鸡建好之后形成的的 $DAG$ 上的顶点；
3. 起始状态 $start/s$，不解释；
4. 接受状态集合 $F$，有 $F\subseteq Q$；
5. 转移函数 $\delta$，即点之间的转移方法；
明白概念即可，下文大概率用不到.
# 贰、终止节点集合与类的亿些特性及证明
对于上文的类有一些特性 ~~并给它们取了名字~~，接下来给出并证明：
## 一、同类即后缀
如果有两个串 $S,T(|S|\le |T|)$（其实取不到等号） 同属一个类，那么一定有 $S$ 是 $T$ 的后缀.
> 证明：$\mathcal Obviously$.
## 二、从属或无关
$\forall S,T(|S|\le |T|)$，他们的 $\text{endpos}$ 集合只有两个情况：
$$
\text{endpos}(S)\subseteq \text{endpos}(T)\space or\space \text{endpos}(S)\cap \text{endpos}(T)=\emptyset
$$
>证明：$\mathcal Obviously$.
## 三、同类长连续
属于同一个类中的所有串，他们的长度一定是连续的，同时，如果按照长度从小到大排序，那么一定有前一个串是后一个串去掉第一个字符的后缀，或者说，后一个串是前一个串在前面加上了一个字符.
> 证明：$\mathcal Obviously$.
所以，如果我们想要储存一个类，只需要存在最短串长度与最长串的长相就可以了.
## 四、类数为线性
类的个数为 $\mathcal O(n)$ 级别的.
> 证明：对于两个类 $\mathcal{X,Y}$，由 "从属或无关" 我们可以知道 $\mathcal{X,Y}$ 要么包含要么不相交，同时，我们也可以找到同一个集合 $\mathcal Z$ 满足 $\mathcal{X,Y}\subseteq \mathcal Z$，那么，我们可以得到 $\mathcal{X,Y}$ 其实是 $\mathcal Z$ 进行了分裂得到的两个类，其实，$\mathcal Z$ 可以一次性分裂成两个或更多个类，但由于我们最开始的集合 $\mathcal Z=\{1,2,3,...n\}$，即 $|\mathcal Z|=n$，由线段树对于集合最多的不交划分结论可知，总类的数量不会超过 $\mathcal O(2n)$，实际上最多 $2n-1$ 个类.
>
> ~~终于不是显然了.~~
## 五，邻类邻长度
对于一个类 $\mathcal X$，如果有一个 $\mathcal Y$ 满足 $\mathcal X\subseteq \mathcal Y$，且不存在 $\mathcal Z$ 满足 $\mathcal X\subseteq \mathcal Z\subseteq Y$，即 $\mathcal X$ 与 $\mathcal Y$ 是直接父子关系，那么有 $\mathcal X$ 中的最短的串 $S$ 与 $\mathcal Y$ 中最长的串 $T$ 满足 $|S|=|T|+1$.
> 证明：对于一个集合的分裂，其实就是在最长的串 $A$ 前面加上一个字符得到新的字符串 $B$，那么，$B$ 的出现的限制条件一定比 $A$ 更强，即 $B$ 所属的类就变成了 $A$ 所属的类 $\mathcal P$ 的子集了，为甚说 $A,B$ 一定不在同一个类中呢？如果在同一类中，那么 $A$ 就不是最长的串而是 $B$ 了，而得到的 $B$ 就是 $\mathcal P$ 的某个子集中最短的一个了，那么就有 $|A|+1=|B|$.
所以，我们只要知道详细父子关系，那么如果我们想要表示一个类只需要存下最长的串的样子就可以了.
# 叁、如何建自动鸡
其实在证明中已经使用了一些类之间存在父子关系的特性了.
定义**直接父子关系**：对于一个类 $\mathcal X$，如果有一个 $\mathcal Y$ 满足 $\mathcal X\subseteq \mathcal Y$，且不存在 $\mathcal Z$ 满足 $\mathcal X\subseteq \mathcal Z\subseteq Y$，那么 $\mathcal X$ 与 $\mathcal Y$ 是直接父子关系.
我们按照类的直接父子关系，建出一棵树，这棵树叫做 $\text{parent tree}$，这个 $\text{parent tree}$ 就是 $SAM$ 的骨架，但是自动鸡只有这棵树似乎什么用都没有，就像 $\tt fail$ 指针基于 $\tt trie$ 树得到 $AC$ 自动鸡一样，我们得在 $\text{parent tree}$ 上加些东西.
首先，根据一些证明的说明，沿 $\text{parent tree}$ 边就是在串的前面动手脚，但是我们还需要在串的后面做手脚，这个时候就需要加入新的边了，表示在串的后面加些字符，这就是自动鸡上面的边.
给出代码，做出进一步说明：
```cpp
/** @brief the size should be two times of the origin*/
int tre[maxn * 2 + 5][30];
int lenth[maxn * 2 + 5];
int fa[maxn * 2 + 5];
/** @brief the number of nodes*/
int ncnt = 1;
/** @brief this variable is necessary, it records the id of the node of the origin string*/
int lst = 1;
/**
* pay attention : node 1 is an empty node, it represent root
* and the length of this node is 0
*/
inline void add(const int c){
// the id of the original string
int p = lst;
// the id of new node or class
int u = lst = ++ ncnt;
// just means the length increases by 1
lenth[u] = lenth[p] + 1; sz[u] = 1;
/** @brief
* if the suffix of the original string
* add a new character @p c hasn't appeared yet,
* then we connect the represent node with the new node,
* it means that we can get a new class if we add @p c to the end
*/
for(; p && !tre[p][c]; p = fa[p]) tre[p][c] = u;
/** @brief
* if all suffixes haven't appeared before after adding @p c
* we'll reach the situation where @p p equals to 0,
* which means the father of the new class is 1(root)
*/
if(!p) fa[u] = 1;
/** @brief if the situation is not like this
* just means some suffixes have appeared before after adding @p c
* which means the new class is a split version of a certain class(actually class @p tre[p][c] )
*/
else{
/** @brief
* of course @p q is the original version of the new class,
* that is, @p q is apparently the father of @p u,
* but there are some other questions that
* some suffixes of @p q will appear at n,
* in other words, some part of @p q will add END POINT @p n (present length),
* which will make a different to class @p q and
* cause the split of class @p q.
* We're going to judge whether @p q should be split or not,
* if the answer is true, we're supposed to handle the split
*/
int q = tre[p][c];
/** @brief
* if all suffix have appeared before after adding @p c ,
* then there's no need to split class @p q ,
* because add END POINT will add n(present length)
* we just need to connect the new class @p u with it father
*/
if(lenth[q] == lenth[p] + 1) fa[u] = q;
/** @brief
* if not, then we're going to find out
* which part of class @p q is going to add END POINT @p n (present length),
* and we split it from here
*/
else{
/** @brief part to add new END POINT
* now node @p q represent a class which won't add new END POINT
* obviously that class @p q and class @p u are the subset of class @p split_part
*/
// pay attention : the new node has no real meaning, so the size shouldn't be added.
int split_part = ++ ncnt;
rep(i, 0, 25) tre[split_part][i] = tre[q][i];
fa[split_part] = fa[q];
lenth[split_part] = lenth[p] + 1;
fa[q] = fa[u] = split_part;
/** @brief
* because the original node @p q is split to two part,
* @p split_part and @p q (another meaning)
* then if an edge which connect a certain node with origin @p q ,
* it is supposed to be changed
*/
for(; p && tre[p][c] == q; p = fa[p])
tre[p][c] = split_part;
}
}
}
```
首先看变量定义：
```cpp
/** @brief the size should be two times of the origin*/
int tre[maxn * 2 + 5][30];
int lenth[maxn * 2 + 5];
int fa[maxn * 2 + 5];
```
$\tt tre[][]$ 表示的即为自动鸡上面的边；
$\tt fa[]$ 表示自动鸡上的父子关系，即我们通过保存父亲节点来维护整个 $\text{parent tree}$；
$\tt lenth[]$ 表示的每个点代表的类中，最长的串有多长；
接下来进入 $\tt add()$ 函数：
```cpp
inline void add(const int c){
```
这个参数 $\tt c$ 表示我们要在串的末尾插入的字符；
```cpp
// the id of the original string
int p = lst;
// the id of new node or class
int u = lst = ++ ncnt;
// just means the length increases by 1
lenth[u] = lenth[p] + 1;
```
$\tt p$ 表示我们在插入 $\tt c$ 之前，代表整个串的点的编号是多少；
$\tt u$ 代表我们要将插入 $\tt c$ 之后，代表新的整个的串的点的编号；
$\tt lenth[u]$ 显然就是在未插入之前的长度基础上增加一；
```cpp
/** @brief
* if the suffix of the original string
* add a new character @p c hasn't appeared yet,
* then we connect the represent node with the new node,
* it means that we can get a new class if we add @p c to the end
*/
for(; p && !tre[p][c]; p = fa[p]) tre[p][c] = u;
```
接下来，我们考虑对于原串 $S$，在增加 $\tt c$ 之后，原来的 $|S|-1$ 个后缀全都有了新的样子（在原来的基础上在末尾加上 $\tt c$），同时，还多出来一个新的后缀——单独一个 $\tt c$，我们称这些东西为**新后缀**，这个循环要做的事情就是，这些新后缀如果在之前没有出现过，那么我们要给他们归为一个新的类——$\text{endpos}=\{|S|+1\}$，同时，显然，后缀越长，它越不容易出现，所以我们从代表 $S$ 的点 $\tt p$ 开始向上走，表示从长到短枚举原来的后缀，对于没出现过的，即 $\tt tre[p][c]=0$，我们将他们连接到新的类——代表 $\text{endpos}=\{|S|+1\}$ 的点 $\tt u$ 上，表示在这些后缀后加上 $\tt c$ 可以到达新的类；
```cpp
if(!p) fa[u] = 1;
/** @brief if the situation is not like this
* just means some suffixes have appeared before after adding @p c
* which means the new class is a split version of a certain class(actually class @p tre[p][c] )
*/
```
如果上一个循坏直接走到空点，也就是说对于原串 $S$ 的所有后缀，在加上 $\tt c$ 之后，在之前的串中都没见过，那么它的父节点就是 $\text{endpos=}[1,n]\cap \mathcal Z$ 的根节点了.
```cpp
else{
/** @brief
* of course @p q is the original version of the new class,
* that is, @p q is apparently the father of @p u,
* but there are some other questions that
* some suffixes of @p q will appear at n,
* in other words, some part of @p q will add END POINT @p n (present length),
* which will make a difference to class @p q and
* cause the split of class @p q.
* We're going to judge whether @p q should be split or not,
* if the answer is true, we're supposed to handle the split
*/
int q = tre[p][c];
```
否则，则说明有些新后缀在之前出现过，即有些后缀的 $\text{endpos}$ 集合不只是 $\{|S|+1\}$，还有些其他的东西，同时，由于之前全部的后缀的点的类中都加上 $|S|+1$ 这个元素，那么此时，仅仅只代表 $|S|+1$ 这个元素的类的点 $\tt u$ 肯定就是其他点的儿子了，那 $\tt u$ 的父亲究竟是谁？显然就是之前循环中第一个不满足条件的 $\tt p$ 的 $\tt tre[p][c]$，我们称这个点为 $\tt q$.
同时，对于 $\tt q$，由于它和 $\tt p$ 并非有实际父子关系，而是由自动鸡连接的 ~~你居然不是我亲生的~~，也就是说 $\tt q$ 代表的串并非全是原串 $S$ 的后缀（但一定会有一个 $S$ 的后缀，即在 $\tt p$ 所代表的后缀之后加上一个 $\tt c$ 的后缀 ），但是我们找到它的原因是什么——它其中的某些串在 $S$ 加上 $\tt c$ 之后，会在 $|S|+1$ 再出现一次，也就是有些串的 $\text{endpos}$ 就会改动，同样的，$\tt q$ 中有些串又不会改动，这下出了个问题——$\tt q$ 所代表的类中的串的 $\text{endpos}$ 集合不一样了，根据定义已经不能再将他们归为同一类，所以接下来我们要考虑将 $\tt q$ 分裂——加上 $|S|+1$ 的部分，和没有加上 $|S|+1$ 的部分；
```cpp
/** @brief
* if all suffix have appeared before after adding @p c ,
* then there's no need to split class @p q ,
* because add END POINT will add n(present length)
* we just need to connect the new class @p u with it father
*/
if(lenth[q] == lenth[p] + 1) fa[u] = q;
```
上文提及，$\tt q$ 中一定会包含一个 $S$ 的后缀，即在 $\tt p$ 所代表的后缀之后加上一个 $\tt c$ 的后缀，但是，如果我们发现 $\tt q$ 类中最长的就是这个后缀（下文称其为**特征串**），由 “同类即后缀” 意味着 $\tt q$ 类中所有串的 $\text{endpos}$ 集合都同时加入 $|S|+1$ 这个元素，那么这个 $\tt q$ 类就没有分裂的必要了；
```cpp
/** @brief
* if not, then we're going to find out
* which part of class @p q is going to add END POINT @p n (present length),
* and we split it from here
*/
else{
/** @brief part to add new END POINT
* now node @p q represent a class which won't add new END POINT
* obviously that class @p q and class @p u are the subset of class @p split_part
*/
int split_part = ++ ncnt;
```
否则，则意味着 $\tt q$ 逃不掉分裂的命运，接下来我们要考虑的是从哪里裂开，先申请一个新的点 $\tt split\_part$ 当作分裂出去的部分（此处认定分裂部分为加上 $|S|+1$ 元素的部分）的编号.
```cpp
rep(i, 0, 25) tre[split_part][i] = tre[q][i];
fa[split_part] = fa[q];
lenth[split_part] = lenth[p] + 1;
```
将 $\tt p$ 的信息继承到 $\tt split\_part$ 上，同时，显然我们分裂的点就是特征串（由 “同类即后缀” 同理可得），显然，原 $\tt q$（没加上元素 $|S|+1$）就是多出 $|S|+1$ 点的 $\tt split\_part$ 类的一个子集，那么可以确定他们有直接父子关系了 （仅仅只多出一个元素，显然不可能找到 $\mathcal Z$ 满足 $\tt q\subseteq\mathcal Z\subseteq \tt \tt split\_part$），那么我们将 $\tt q$ 的父亲设置为 $\tt split\_part$，同样，只有一个元素 $|S|+1$ 的 $\tt u$ 类的父亲肯定也是 $\tt split\_part$ 类了.
```cpp
/** @brief
* because the original node @p q is split to two part,
* @p split_part and @p q (another meaning)
* then if an edge which connect a certain node with origin @p q ,
* it is supposed to be changed
*/
for(; p && tre[p][c] == q; p = fa[p])
tre[p][c] = split_part;
```
但是，我们确实是将 $\tt split\_part$ 分裂出去了，但是，这个 $\tt split\_part$ 是代表原来的 $\tt q$ 的，但是还有一些点是沿着自动鸡连接在旧的 $\tt q$ 上，我们要将他们改过来，将他们和 $\tt split\_part$ 连接.
然后，插入新点结束，构建自动鸡时只需：
```cpp
rep(i, 1, n) add(s[i] - 'a');
```
贴一发整合代码：
```cpp
const int maxn = 1e6;
int tre[maxn * 2 + 5][30];
int lenth[maxn * 2 + 5];
int fa[maxn * 2 + 5];
int sz[maxn * 2 + 5];
int ncnt = 1;
int lst = 1;
char s[maxn + 5];
int n; // the length of string s
inline void input(){
scanf("%s", s + 1);
n = strlen(s + 1);
}
inline void add(const int c){
int p = lst;
int u = lst = ++ ncnt;
lenth[u] = lenth[p] + 1;
for(; p && !tre[p][c]; p = fa[p]) tre[p][c] = u;
if(!p) fa[u] = 1;
else{
int q = tre[p][c];
if(lenth[q] == lenth[p] + 1) fa[u] = q;
else{
int split_part = ++ ncnt;
rep(i, 0, 25) tre[split_part][i] = tre[q][i];
fa[split_part] = fa[q];
lenth[split_part] = lenth[p] + 1;
fa[q] = fa[u] = split_part;
for(; p && tre[p][c] == q; p = fa[p])
tre[p][c] = split_part;
}
}
}
signed main(){
input();
rep(i, 1, n) add(s[i] - 'a');
}
```
# 肆、复杂度分析
## 一、点数线性
点数即类数，上文已证明，最多 $2n-1$ 个 类/点.
## 二、边数线性
考虑自动鸡有以下性质：
- 从 $s$ 开始，沿不同的路径，最终一定会走到不同的子串；
- 由 “同类即后缀”，以及 “同类长连续”，可以说明，只要这个类中有一个串是整个串的后缀，那么整个类都是串的后缀（其实从另一个角度说，同一个类中的串，区别只在于他们在前面加字符，但是在后面的字符是不动的）
然后，我们进行一个定义：定义**广义环为忽略边的方向，将所有边视为无向边之后形成的环成为广义环.**
现在，我们可以开始证明边数不超过 $3n-4$ 了.
首先，假设我们有了一个自动鸡，但是他们还没有连边，我们从 $s$ 开始走后缀，现在规定走后缀的规则：
1. 每次走后缀只有一次花费；
2. 如果走的边和原来的边没有形成广义环，那么我们走这条边并将这条边添加进自动鸡，并且这条边不会使用花费；
3. 如果走的边和原来的边形成了广义环，那么我们走这条边并将这条边添加进自动鸡，并且使用花费；
如果我们沿这些规律走后缀，最后最多只会有 $3n-4$ 条边，
## 三、$\tt add()$ 函数复杂度证明
我再贴一个代码：
```cpp
inline void add(const int c){
int p = lst;
int u = lst = ++ ncnt;
lenth[u] = lenth[p] + 1;
for(; p && !tre[p][c]; p = fa[p]) tre[p][c] = u;
if(!p) fa[u] = 1;
else{
int q = tre[p][c];
if(lenth[q] == lenth[p] + 1) fa[u] = q;
else{
int split_part = ++ ncnt;
rep(i, 0, 25) tre[split_part][i] = tre[q][i];
fa[split_part] = fa[q];
lenth[split_part] = lenth[p] + 1;
fa[q] = fa[u] = split_part;
for(; p && tre[p][c] == q; p = fa[p])
tre[p][c] = split_part;
}
}
}
```
其实这里就几个循环，而对于前两个，我们都是在加边，但是由于我们边数已经是 $3n-4$ 的上界了，那么这俩循环加起来总共也不超过 $3n-4$，但是我们考虑我们的第三个循环：
```cpp
for(; p && tre[p][c] == q; p = fa[p])
tre[p][c] = split_part;
```
这个不好分析，我们考虑整个 $\tt add()$ 在干什么：
1. 从 $lst$ 向上爬，这个过程会减小**可能成为 $u$ 的** $\tt fa[u]$ 的 $\text{minlen}$(就是类里面最小的字符串长度)；
2. 爬到头了，从 $p$ 走到 $q$，这个过程会让**可能成为 $u$ 的** $\tt fa[u]$ 的 $\text{minlen}$ 不多不少 $+1$；
3. 给 $u$ 认父亲，然后让 $u$ 变成 $lst$(也就是下一次的 $u$)；
我们发现，每次 $fa[u]$ 的 $\text{minlen}$ 最多只会增加一，但是减少却可能一次性减少很多，这类似于 $\tt SA$ 求 $\text{heit}$ 数组的过程，那么总复杂度大概在 $\mathcal O(n)$ 级别.
实际上，如果我们将 $\text{minlen}(fa[u])$ 当成势能函数，可能会更好理解.
# 伍、应用
部分引自 $\tt oi-wiki$，对于部分 ~~我知道的~~ 可以使用 $SA$ 解决的也会大致描述，同样，如果有其它如使用 $\tt kmp$ 的巧妙方法亦会大致描述.
## 一、检查子串
- 使用 $SAM$：
检查 $T$ 是否是 $S$ 的某个子串.
后缀自动鸡中实际上保存了 $S$ 的所有子串信息，所以你只需要从开始节点沿自动鸡边走就可以了.
- 使用 $SA$：
将 $S$ 和 $T$ 拼在一起，中间用分隔符隔开，判断 $\text{heit}$ 即可.
## 二、本质不同串个数
- 使用 $SAM$：
$SAM$ 沿自动鸡边走形成的串本来就是本质不同的子串，所以，我们只需要统计从开始节点走的不同路径数，由于是 $DAG$，可以直接跑拓扑 $DP$.
- 使用 $SA$：
每个后缀长度减去 $\text{heit}$ 之和.
## 三、第 k 大子串
[这里有板题 OAO](https://www.luogu.com.cn/problem/P3975)
- 使用 $SAM$：
如果是去重，那么每个点的 $sz$ 定为 $1$，即表示每个字串都只出现一次而不因 $\text{parent tree}$ 树的出现而改变，反之，$sz$ 即为其 $\text{parent tree}$ 子树的大小.
然后，我们处理出一个 $\tt sum$ 数组表示经过这个点的子串有多少，那么就有
$$
sum[u]=sz[u]+\sum_{v\in tre[u]}sum[v]
$$
处理出来之后用类似 $\tt trie$ 树的做法即可.
- 使用 $SA$：
如果是去重，处理出 $\tt SA$ 之后，由每个后缀都有 $n-sa[i]+1-heit[i]$ 个本质不同的子串，然后就可以解决.
如果是非去重，这里直接引用 [大佬](https://www.luogu.com.cn/user/48147) 的解决方案.
>因为我们前面的字母是确定的，那么当前面的字母一样的时候，后面一个字母一定是单调不下降的。
>
>那我们就能二分求出这个字母最后一个的位置。
>
>我们建一个后缀长度的前缀和，那我们就能求出以这个字母开头的子串有多少个。
>
>当个数大于 $k$ 时，就确定了这个字母，否则 $k$ 减去，继续枚举下一个字母。
>
>枚举完一位继续下一位，那我们就能把范围缩小，知道求出答案。
实际上本质和 $SAM$ 的做法差不多.
## 四、二元最长公共子串(LCS)
- 使用 $SAM$：
对于一个串建立 $SAM$，拿另一个串在 $SAM$ 上能跑多远跑多远，跑不了了就往父亲跳.
- 使用 $SA$：
两个串用 $SA$ 经典~~流氓~~做法接在一起（注意中间用分隔符隔开），处理出 $\tt sa$ 之后将 $\tt heit$ 排序从大到小枚举长度，直到一个属于两个串的 $\tt heit$ 满足标准后就找到长度（如果要找长什么样子也可以，这里不做赘述）.
## 五、最小循环位移
- 使用 $\tt kmp$：
先找到 $n$ 位置对应的 $nxt$，那么最小循环位移就可能是 $n-nxt[n]$，检查一下，如果不满足就 $GG$.
- 使用 $SAM$：
复制一个 $S$ 并对其建立 $SAM$，然后在 $SAM$ 上寻找最小的长度为 $|S|$ 的路径即可.找最小的，我们只需要贪心往最小字符走即可.
- 使用 $SA$：
理论上可以当 $\tt kmp$ 用，我们对于反串排出 $\tt sa$，然后看 $S'[1...n]$ 的位置，那么长度要么就是它和它前一名、要么就是它和它后一名的 $LCP$，然后我们暴力检验就可以了.
## 六、子串出现次数
- 使用 $SAM$：
找到子串对应的点，然后算出这个点的 $sz$ 就可以了.
- 使用 $SA$：
用流氓做法，把子串接在后面然后处理出 $\tt sa$，然后看属于两个串的 $heit$ 刚刚好是子串长度的 $heit$ 个数即可.
## 七、多元最长公共子串(exLCS)
- 使用 $SAM$：
两种思路：
1. 对于第一个建立 $SAM$，然后其他的在这个上跑，对于每个点，记录 $f[i]$ 表示走到 $i$ 能够匹配上的最长公共子串的长度，注意 $f[i]\le \text{longest}(i)$，最后跑拓扑，用 $f[i]$ 更新 $f[fa[i]]$，得到匹配完某个串之后的 $f[]$，然后记录在 $ans[i]$ 中，其中 $ans[i]$ 表示第 $i$ 个点的**历史中**能匹配的最小长度（因为我们要求的是满足所有的串），最后在 $ans[i]$ 中找最大就可以了.
2. 设 $T=S_1+D_1+S_2+D_2+...+D_{n-1}+S_n+D_n$，其中 $S_i$ 是我们想要找的，$D_i$ 是对应的分隔符，我们对于 $T$ 建立 $SAM$，然后，如果 $S_i$ 中有一个子串，那么存在一条路径从 $D_i$ 不经过其他的 $D_j$ 的路径. 然后我们处理连通性，使用 $\tt BFS$ 等搜索算法之族以及动规计算，然后，答案就是所有的 $D_i$ 都能到达的点中 $\text{longest}$ 的最大值.
- 使用 $SA$：
流氓将所有串暴力接起来，从大到小枚举 $heit$ 长度，并用并查集枚举每一个合并的块中有多少不同的集合，当某个连通块中存在了所有的串，此时枚举的长度就是答案串的长度，寻找就随意了.