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