一些对于SAM的理解

· · 算法·理论

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

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

  1. 把转移压缩（字符转移变为字串转移），这个对应后缀树。
  2. 压缩状态（找到等价类进行划分），这个对应后缀自动机。

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

  1. 对于两个子串 s 和 t，s 与 t 的关系只有包含或并列两种可能，绝对不会相交。
  2. 一个等价类中的子串长度连续。
  3. 等价类的数量是 O(n) 级别的。

第三点的证明可以用一种叫做 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。因此我们要进行讨论：

  1. 只有 p 转移到 q (此时 len(q)=len(p)+1)，直接在 q 的 endpos 集合中插入 |S| 即可，不用进行进一步修改，那我们也只需要将新节点的 link 指向
  2. 不只有 p 转移到 q，显然需要一个全新的等价类，我们直接新创建一个等价类 clone，很显然地， p 和从 p 继续往上跳的且能转移到 q 的点，都会指向新建节点 clone，因为这才是它们转移到的等价类，而原来 q 所代表的 endpos 集合就成为了 clone 的真子集，根据定义 link 自然要指向 clone，新节点的 link 也同理，由于只新增了一个字符，那么加入一个不同字符的转移一定不会有以 |S| 位置为结尾的后缀，如果存在，那么一定是形如 aaaaa 的串，但很显然这会被情况 1 处理掉，所以 q 的所有转移放在 clone 上全部成立，至于 clone 的 len，由于只有 p 及其往上跳的部分点会转移到 clone，所以自然是 len_p+1。

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

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