零、关于后缀自动鸡的一些牢骚废话和引入
它取名叫后缀自动鸡，但是实际上在一个自动鸡出炉之后好像和后缀基本上没什么关系，按照 \(\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}\))；
- 自动鸡不是 算法/数据结构，只是一种数学模型，对于同一个问题可能有很多只鸡，但是不是所有的鸡都满足我们解决问题时的资源消耗（比如时间和空间）；
同时，一只鸡由这几个部分组成（虽然下文不会用到）：
- 字符集 \(\Sigma\)，表示这只鸡只能输入这些字符；
- 状态集合 \(Q\)，即在自动鸡建好之后形成的的 \(DAG\) 上的顶点；
- 起始状态 \(start/s\)，不解释；
- 接受状态集合 \(F\)，有 \(F\subseteq Q\)；
- 转移函数 \(\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)\).
终于不是显然了.
五，邻类长连续
对于一个类 \(\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\) 的骨架，