一些对于SAM的理解

对于构造需要满足的要求就先省略了。

如果不考虑时空限制的话，后缀Trie是一个很方便的实现方式，但是其时空复杂度都是 $O(n^2)$ 的，并不是很能接受。 有两个方向：

现在我们考虑第二种优化方法，这时我们引入 endpos 的概念，我们用 $endpos(t)$ 表示字符串 $t$ 在字符串 $S$ 中出现的所有位置的末位置的集合， endpos 集合相同的子串归为一个等价类。这一定义能带来很多优秀的性质，比较重要的包括：

第三点的证明可以用一种叫做 parent tree 的树，实际上就是根据第 1 条的性质画出的树结构，并且这种结构保证状态数在 $O(n)$ 级别。

但我认为最巧妙的是后缀自动机的构造，这是一个在线的过程，看起来很不可思议，每动态插入一个字符，就相当于加入一堆新后缀，就要新接许多转移边，就会导致一系列等价类集合更新，似乎不是很能做到快速更改。

然后这里就一直不是很能理解，后来在某处看到了自动地这个词，突然领悟了一些。

我们从来没有维护过 endpos 集合的具体位置，为什么呢，因为这个集合是会自动更新的，当你进行插入时，它就已经改变了，并不需要手动修改。

然后再回过头来看插入操作，最长的那个串 $|S|$ 一定会形成一个新的等价类 $\left \{ |S| \right \}$ ，而 $p$ 一路往上跳，如果都不存在到新字符 $c$ 的转移边，那么这些新形成的子串的 endpos 集合均为 $\left \{ |S| \right \}$，显然是从空集引出的，所以新节点的 $link$ 指向源点。假如一路跳到了头，那么就只产生了这个新状态，而转移边已经全连上了。

如果上跳过程中存在一个位置 $p$ 且 $p$ 有 $c$ 这条转移边，转移到了 $q$ ，那么很明显，由 $p$ 转移到的 $q$ 的 endpos 集合中会自动加入 $|S|$ 这一元素，但是，不一定只有 $p$ 能转移到 $q$。因此我们要进行讨论：

那么至此插入的三种情况全部解决，只需要把 $last$ 改为新节点的编号就行，插入过程就圆满完成了。

这算是我对后缀自动机的理解过程吧，状态数证明和一些细节的证明还没有深入探究，以后再继续深入。