后缀自动机学习.docx

后缀自动机实质上是字母树, 记录的字符串是某个字符串s 的所有后缀. 这里以字符串 ACAD D 为例: 这样很浪费空间和时间( 实际上都是 O(n^2)). 但是, 注意: 这棵字母树的结点虽然多, 但大部分结点都只有一个儿子, 而且有很多段是一样的. 那么, 利用公共部分, 就可以对空间进行压缩, 具体地说, 就是把自己连到儿子的边删掉( 并把该儿子及其后代删掉), 再把这条边连到别的子树,这样就能充分利用公共部分, 节省空间. 但是, 如何保证这样做和原来的笨做法是等价的, 又如何把时间复杂度和空间复杂度降到 O(n)? 这是个问题. 幸运的是, 后缀自动机出现了. 后缀自动机是这样的: 在后缀自动机中, 为了节省空间, 某个点有可能成为多个结点的儿子,可以保证在后缀自动机中遍历出来的所有字符串不会重复, 而且刚好是原串 s 的所有子串. 先讲讲后缀自动机的大致做法: 假设当前已经建好了 s 的某个前缀的后缀自动机 t, 那么就要通过某种算法, 添加一个字符 x,得到s 另一前缀tx 的后缀自动机, 这样每次插入一个字符, 最后把s 的所有字符按顺序插入完毕就得到了 s 的后缀自动机. 这样的话, 建造后缀自动机的过程是在线的, 就是说, 可以任意时刻询问 s 的某些信息, 也可以任意时刻在 s 的结尾插入一些字符, 变成新的字符串. 不过, 删除是不支持的. 在后缀自动机中, 每个结点储存的信息有: son[26]: 返回该结点对应的子串加上某个字符后生成的合法子串在后缀自动机中所对应的位置( 其实就和字母树一样), 如果该指针不存在, 就说明这样的子串是不存在的( 即不是s 的子串) pre: 注意这不是返回它的父结点( 因为某个点有可能成为多个结点的儿子), 而是返回上一个可以接收后缀的结点( 如果当前结点可以接收新的后缀, 那么 pre 指向的结点也一定可以接收后缀). step: 返回的是从根结点走到该结点, 最多需要多少步. 为了方便下面的叙述, 这里先提出三个后缀自动机的性质: ①从 root 到任意结点 p 的每条路径上的字符组成的字符串, 都是当前串 t 的子串. ②因为满足性质一, 所以如果当前结点 p 是可以接收新后缀的结点, 那么从 root 到任意结点 p 的每条路径上的字符组成的字符串, 都是必定是当前串 t 的后缀. ③如果结点 p 可以接收新的后缀, 那么 p的 pre 指向的结点也可以接收后缀, 反过来就不行. 下面的叙述中, 将直接应用这两个性质. 当前建立的后缀自动机是对应字符串 t的, 现在要插入字符 x,把t 的后缀自动机变成 tx 的后缀自动机. 首先建立储存当前字符 x 的结点 np, 找到之前最后一个建立的结点( 因为它一定满足性质②), 然后就不断按 pre 指针跳( 直到跳到有 x 儿子的结点为止). 假设当前跳到p 结点,如果p没有x 儿子, 那么它一定可以接收新来的字符, 然后就把p的x儿子赋值为 np( 这时,p 接收了后缀字符 x, 目前已经不可以接收新的后缀字符了). 然后, 就要处理有x 儿子的结点了, 假设 p的x 儿子是 q. 只有 2 种情况: ① step[q]=step[p]+1. 因为我们要后缀自动机的结点尽量少, 所以要尽量共用一些信息. 这是对应的图: 这时,p 点