后缀自动机学习.doc

后缀自动机学****br/> 后缀自动机实质上是字母树,:
这样很浪费空间和时间(实际上都是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
:
①step[q]=step[p]+1.
因为我们要后缀自动机的结点尽量少,:
这时,p点是满足性质②,如果可以把np直接接到p后面,就可以省下很多空间了,但是因为q点的存在, np不能直接接到p后面,否则p-?就是说q可不可以像n