后缀自动机

后缀自动机

$endpos$ 一个子串$p$在原串中出现的位置的右端点标号组成的集合，我们称之为 $endpos(p)$

关于$endpos$的性质:

1.如果两个子串$endpos$相同，则其中一个必然是另一个的后缀

2.对于任意两个子串$t$与$p$($len_t\leq len_p$),要么$endpos(p)\in endpos(t)$,要么$endpos(t) \bigcap endpos(p)= \emptyset$

3.对于$endpos$相同的子串，归于一个$endpos$等价类。对于任意一个$endpos$等价类中,子串长度连续。

4.$endpos$等价类个数级别为$O(n)$

5.在parent tree中,$maxlen(fa(a))+1=minlen(a)$

6.后缀自动机边数$O(n)$

现在，目标:在parent tree上建边，使得源点(空串)到parent tree上一点x的路径形成的字符串都在endpos(x)类中

important 点之间有father-son关系，到点$i$的字符串$p$，与到点$fa(i)$的字符串$q$，满足$length(q)<length(p)$,且$q$为$p$的后缀。