后缀自动机 (suffix automaton, SAM) 是一个能解决许多字符串相关问题的有力的数据结构。(否则我们也不会用它)
举几个例子，以下的字符串问题都可以在线性时间内通过 SAM 解决
1.在另一个字符串中搜索一个字符串的所有出现位置。(诶？KMP好像能做)
2.计算给定的字符串中有多少个不同的子串。(诶？好像也能做)
3.统计一个子串所有不同子串的总长度 (额，线性复杂度？以前的知识好像就不行了)
4.字典序第k大/小子串(字典树好像可以做，但线性？不会！)
5.给定一个字符串 。找出字典序最小的循环移位。(这个我会！最小表示法！)
6.对于一个给定的文本串T ，有多组询问，每组询问给一个模式串S ，回答模式串S在字符串T中作为子串出现了多少次。(AC自动机！也可以)
7.给定一个字符串S 和一个特定的字符集，我们要找一个长度最短的没有在S中出现过的字符串。(以前的知识做不到我太菜了)
8.两个字符串的最长公共子串(线性？？！以前的知识做不到我太菜了)
9.多个字符串的最长公共子串(我不会！！)
这么多东西都可以线性时间内解决，厉害吧；
厉害的前提是你先要学会后缀自动机
接下来进入正题：
1.SAM 是一张有向无环图。结点被称作 状态 ，边被称作状态间的 转移 。
2.图存在一个源点root称作 初始状态 ，其它各结点均可从root出发到达。每个 转移 都标有一些字母。从一个结点出发的所有转移均 不同 。
3.存在一个或多个 终止状态 。如果我们从初始状态出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串S的一个后缀。
4.S的每个后缀均可用一条从到某个终止状态的路径构成。
5.在所有满足上述条件的自动机中，SAM 的结点数是最少的。
具体可以证明，SAM的点数最多是2*n-1,边数最多时3*n-4； （暂时为了方便理解并不证明，你只要露出"哇！这是上限吗"，"我靠，这SAM的复杂度也太***的强了"的表情就好了）;
SAM 最简单、也最重要的性质是，它包含关于字符串的所有子串的信息。任意从初始状态开始的路径，如果我们将转移路径上的标号写下来，都会形成S的一个子串 。反之每个S的子串对应从初始状态开始的某条路径。
为了更好的理解SAM（背模板，水经验），我们定义一些奇怪的东西；(不要一看到不认识的概念就跳过去，否则建图会看不懂的)
1.endpos等价类
考虑字符串S的任意非空子串t，我们记endpos(t)为在字符串S中t的所有结束位置.
让我们举个栗子：（假设对字符串中字符的编号从零开始）
对于S=“cbacbaba” endpos(ba)="2,5,7" endpos(a)="2,5,7" endpos(cba)="2,5";
我们发现，对于"ba"和"a"的endpos等价类的数值是完全相同的，那么这对与SAM来说是个好东西，我们可以将所有endpos相同的子串放到SAM的一个节点上，大大节省了空间与时间复杂度；
原文：https://www.cnblogs.com/kamimxr/p/12056278.html