本蒟蒻初识后缀自动机,如有缺漏,请指出,感激不尽。

什么是后缀自动机

后缀自动机是一个有向无环图,节点为状态,有向边为状态转移。其中有一个初始状态可以到达所有状态,若干个结束状态,从初始状态走到一个结束状态,就是原本字符串的一个后缀

它大约长这样:
字符串ACADD:
后缀自动机
图来自这位dalao

如何构造后缀自动机

建议静下心来,结合后面的代码进行理解。
假设现在已经构建好了前len个字符的后缀自动机(前len个字符组成的串称为当前串),我们要插入一个新字符x进去,那么我们要实行“三步走”的发展战略
首先,我们确定几个概念:

可接受节点:若p是一个可接受节点,那么从root到p的每条路径上的字符组成的字符串,都是当前串的一个后缀。因此,在加入一个新字符时,这个节点后面可以连一个新节点,增长后缀。
儿子:每个节点可以直接到达的节点
pre指针:某个节点的上一个代表字符与其相同的可接受节点。节点p之后的结束位置(即作为原串后缀结尾的节点)是其pre的真子集。
step:从根节点到某个节点最多要走的步数
重要定理:假如字符x的上一位是字符y,插入x后,每个代表字符是y的可接受节点后面都应该接上新点。

好了,如果明白了以上概念,我们就可以开工了!
1.建立一个新节点np
2.找到之前最后一个建立的节点last,那么last一定是一个可接受节点。顺着last的pre指针依次往上跳,这些节点一定也是可接受节点。所以如果这些节点没有x儿子,那么就让它们的x儿子为np
代码表示如下:

3.跳到某一个节点p,它有x儿子了。怎么办?
p的x儿子为q,分两种情况:
  3-1.如果$step[q]=step[p]+1$,这时,从根节点出发到q,一定会经过p,且中间不夹杂其他字符。由重要定理,p的后面应该接上一个x,那么可以将q视作这个x,而当前x对应的节点一定会是可接受节点,所以q就成了一个可接受节点。因此,令$pre[np]=q$即可。
  代码表示:

  3-2.如果$step[q]> step[p]+1$。由于这种情况不太好处理,所以我们可以将其转化为3-1
  具体做法是新建一个节点nq代替q强行使得$step[nq]=step[p]+1$。那么将q的儿子指针和pre指针都拷贝给nq,然后(准确来说是最后一步)顺着ppre指针往上走,将那些x儿子是q的节点的x儿子都改成nq。
  那么nppre就是这个代替了q的nq啦~\(≧▽≦)/
  而由于和3-1中的q是可接受节点一样的原因,nqq都是可接受节点,所以qpre指针指向nq
  代码表示:

完整版代码:

后缀自动机的基本应用

现在我们造出了一台后缀自动机,我们要把它应用于生产实践之中了!
后缀自动机的几个性质:
性质1:从root出发在上面瞎走几步,可以得到一个子串。而且如果走完所有走法,那么可以得到所有子串。
性质2:后缀自动机是一个有向无环图,可以进行拓扑排序。
性质3:出现次数向父亲传递,接收串数从儿子获取
由以上两个性质,我们会发现后缀自动机上可能经常要求递推和dp。
以下基本上是clj的ppt上的例题=_=
洛谷P3804:由pre指针的定义,可知用pre指针相连的节点在原串中可以视作同一字符,所以按照拓扑序逆序处理子串的出现次数,而子串长度就是step。

spoj-NSUBSTR:用上一题的方法获得sz值就可以了。
bzoj2555:使用lct去维护上面的sz值......码力不足的本蒟蒻调试了三个小时......
poj1509:把字符串复制一份贴到后面,然后插入到后缀自动机里,由性质1,从根节点出发走length(字符串长度)步即可获得最小字典序循环节。
因为我们是走了length步到达当前节点的,所以当前节点的step一定大于等于length。假设step不代表这个节点的字符在字符串中的位置,那么一定存在一个和当前这个长度为length的子串长得一样的串,在当前子串的前面。这样我们找到的就应该是那个串的结束节点,与假设矛盾。所以step代表这个节点的字符在字符串中的位置,答案是$step[p]-length+1$
SPOJ - SUBLEX:注意,并不是在任何情况下step都代表这个节点的字符在字符串中的位置(本蒟蒻就因为这个WA了......)
令$dp$表示从这个节点往后还能生成多少子串,逆拓扑序计算一遍后就很好处理了。
spoj-LCS:对于字符串A建立后缀自动机,然后用B去遍历该自动机。如果走到某个节点,它有x儿子,就走到x儿子,当前匹配长度+1。否则顺着pre指针往上找到一个有x儿子的节点p,当前匹配长度为step[p]+1,再走到p的x儿子。如果找不到,就走到根,匹配长度为0。
spoj-LCS2:对于第一个字符串建立后缀自动机,然后用其他字符串去用上题类似方法遍历。
我们令g:以该节点代表的字符结尾的子串,在本次匹配中的最大匹配长度,f:每次用一个新字符串去后缀自动机里匹配的g的最小值。
显然答案是所有f里的最大值。
注意的是,在后缀自动机上,某节点的匹配结果也应该是它的pre的匹配结果,所以还要更新pre。