后缀自动机学习.doc

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