后缀自动机是个很神奇的数据结构。
首先我们知道的是我们需要一个能够描述所有后缀的数据结构。
然后就有人发明了后缀自动机、后缀树、后缀数组、$\dots$
首先介绍一些后缀自动机的概念。
记$right(s)$表示子串s在整个串中的结束位置集合。
节点u表示某些right相等的子串们，可以注意到它们肯定互为后缀。
那么，可证如果s为t的后缀，那么$right(t)\subseteq right(s)$。
记$max(u)$表示它们中最长的一个，$min(u)$表示它们中最短的一个。经过证明可以发现它们的长度还是连续的。（然而我不会证）
证明：
考虑$max(u)$的后缀s使得$len(min(u))\leq len(s)\leq len(max(u))$，那么我们要证明s属于u表示的子串们。
因为s为$max(u)$的后缀，所以$min(u)$为s的后缀，
所以$right(min(u))\subseteq right(s)\subseteq right(max(u))$，
又因为$min(u)$和$max(u)$的right相等，
所以$right(min(u))=right(s)=right(max(u))$。
即s也在u表示的子串内。
证毕。
go：$go(u,c)$表示从节点u的所有节点加上一个c字符走到的节点。
link：考虑$min(u)$，其删掉第一个字符后得到的串肯定不是u所表示的串，但是其肯定是在某一个节点所表示的串中的，就记那个节点为$link(u)$。
然后就考虑怎么构造这个后缀自动机了。
如果现在已经构造出了原串$S$的一个前缀$T$，现在要加入最后一个字符c，那么现在的新加入的子串就是$Tc$的一个后缀了，也是$T$的一个后缀（但这时候可以为空）加上c。
考虑新加上的节点是np，上一次加入的节点是p，那么找到第一个p的祖先使得有$go(p,c)$，因为我们需要找到一个当前新串的后缀在前面出现过的地方。
如果实在没有那就算了，将当前节点的link挂到root那里去
否则当前节点的父亲不出意外应该是$q=go(p,c)$，但是经常会出意外（逃：
如果$len(max(p))+1\neq len(max(q))$，则说明如果我们想将最后一个c硬插入到q的后面，会发生一些奇怪的事情。。。比如说q表示的串出现次数和其它的不一样什么的。所以我们需要把这个q节点分裂成两个。一个是nq，表示将max(p)加上一个c，另一个是原来的np，表示Tc的后缀。这两个的出现位置是不一样的。然后q和np的link都是应该连向nq的。
（其实这里还是没有特别懂。。。
然后对于表示其他的子串加上c的那个节点，我们应该将它的父亲设为那个T的后缀（明显这个的长度大于等于那个后缀），然后将从T最长的后缀开始到最短的后缀的所有go都更新一下。