本文主要是记录自己在学后缀自动机过程中觉得比较重要的东西,不可作为从零学习后缀自动机的资料。

定义

字符串S的SAM是一个接收S的所有后缀的最小DFA。
DFA是确定有限状态自动机。(这个不知道建议李军辉老师把我编译原理挂了)
节点和节点之间用转移(边)连接,边有边权(字符)

特点

对于每一个终止状态,从初始状态t0该终止状态所有的边权一定是S的一个后缀。
这里来个图方便理解。一个具体的SAM

构造

定义

结束位置:对于S任意的非空子串T,endpos(T)为S中T的所有结束位置(假设字符串字符编号从1开始)。
对于字符串S=”abcbc”。endpos(“bc”)=(3,5)
同理endpos(“c”)=(3,5)

等价类:若子串T1,T2的endpos相同则这两个子串属于一个等价类,整个字符串S被划分为若干的等价类。

由上面可知,SAM的状态数是子串等价类的个数加上一个初始状态。

引理

先假设字符串S的两个非空子串u和w(|u|<=|v|)
引理1:若u和w的endpos相同,则u在S中每次出现都是以w的后缀形式出现的。
解释:如果u和w的endpos相同,则u是w的一个后缀,且只以S 中的一个w的后缀的形式出现。且根据定义,如果u为w 的一个后缀,且只以后缀的形式在S中出现时,两个子串的endpos相同。

引理2:那么要么endpos(u) ∩ endpos(w) = Ø ,要么endpos(u) ∈ endpos(w) ,取决于u是否为w的一个后缀
解释:如果endpos(u) 与 endpos(w) 至少有一个元素相同,则表示他们在某一个位置结束,则u是w的后缀。

引理3:考虑一个endpos等价类,将类中的所有子串按长度非递增的顺序排序。每个子串都不会比它前一个子串长,与此同时每个子串也是它前一个子串的后缀。换句话说,对于同一等价类的任一两子串,较短者为较长者的后缀,且该等价类中的子串长度恰好覆盖整个区间[x,y]。
读者自证不难。