缘起
上一篇【1】我们学习了SAM的基本概念. 通过转移函数知道了SAM的工作原理.现在来进一步做题. hihocoder #1445 : 后缀自动机二·重复旋律5 , 注意, 为保证循序渐进, 墙裂推荐先学习【1】再来看本文. 会发现本文是那么的自然.
分析
本题其实就是告诉你一个字符串S, 然后问你S的所有不同子串的个数. 而根据【1】的学习, 我们知道答案就是
所以我们必须构建出SAM. 但是字符串的长度达到了 1e6, 所以必须采用 O(len(S))的SAM构造算法. 本文的目的就是学习SAM的线性时间构造算法.
和后缀树一样, 我们打算采用增量的观点来构造SAM. 所谓增量的观点就是每次读入一个字符. 则会新产生一些要识别的后缀. 然后我们就必须对现有的SAM进行改造. 最终等到所有的字符都读完之后, 整个字符串的SAM就构造好了. 举个例子——我们要构造 S="abaab" 的SAM, 则从空串开始，空串对应的SAM就是SAM的0起点. 然后依次读入a、b、a、a、b 这5个字符, 每次都会对既有的SAM进行升级改造. 读完最后的b并且升级改造完毕就得到了S="abaab"的SAM. 因为我们需要O(n) 构造算法. 所以我们不难想象, 每次的升级改造SAM的时间必须控制在O(1)内. 这个时候, 你就会发现后缀link(下面简称slink)帮了大忙——所以【1】中才说slink是SAM的大杀器.
好了, 现在来看看假如我们已经读完了S[i]并且升级改造完毕了SAM. 假设S[1,...,i]位于的节点是u. 现在需要读入S[i+1]这个字符. 则我们新增的需要识别的后缀是 S[1,...,i+1], S[2,....,i+1], S[3,....,i+1],..... S[i,i+1], S[i+1]. 而这i+1个后缀恰好就是 S[1,...,i]、S[2,..,i]、...、S[i]、空串这i+1个后缀拼上S[i+1]形成的. 而根据【1】的学习, 我们知道S[1,..,i]、S[2,...,i]、...、S[i]、空串这i+1个子串属于若干等价类, 而且这些等价类对应的sam节点之间通过slink连接, 而且沿着slink恰好走到sam的起点0(按照【1】中的描述, 删光了所有S[1,..,i]中的字符变成了空串, 空串对应的节点就是sam起点0). 其中 S[1,...,i] 属于的节点称作u, 则这条沿着slink的路径就是从u出发, 一直走到sam的根节点0的路径. 我们称之为 slink-path(u)
下面直接贴本题代码, 后面会有详细注释
下面解释一下上面的代码
通过本题，我们就能体会到为什么slink是SAM能O(n) 构建的保证了. 因为我们每次升级改造的过程本质上是完成识别S[1,...,i+1]、S[2,....,i+1]、....、S[i, i+1]、S[i+1]的任务——所谓的识别也就是给这i+1个后缀都找到归属的节点——如果找不到就新建SAM节点. 如果没有slink的话, 我们就要逐个去考察这些后缀, 看看他们属于哪个节点. 一旦这样, 算法就膨胀为O(N^2)的了. 而后缀link的最大也是唯一作用在于已经帮我们维护好了S[1,...,i]、S[2,...,i]、 .....S[i-1,i]、S[i]、空串 的归属了(而我们要新增的i+1个后缀恰好就是这i+1个后缀后面拼接上S[i+1]这个字符而已)——类似于分块的思想. 而且他们之间的归属通过slink已经帮我们维护好了. 我们通过slink就可以快速的从一个节点跳到另一个节点, 就不需要傻傻的一个一个的遍历这些后缀了. 复杂度就降低为O(n). 这就是slink的威力! 其实对比后缀树的ukk算法，也都用到了类似的思想——就是快速维护. 后缀树的构建也用到了后缀链接的思想.
参考
【1】《史上全网最清晰后缀自动机学习(一)基本概念入门》
附录(虚线箭头是slink,实线箭头是trans)
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。
