头部背景图片
Decaku 's Blog |
Decaku 's Blog |

后缀自动机学习笔记

后缀自动机学习笔记

  • 前言:本篇文章只是简单的记录一下自己对于SAM的理解,可能并不太准确,其中有些细节也没有详细的论证过程,详细证明可以参考陈立杰的PPT。

定义

后缀自动机是能够识别一个字符串所有后缀的最小有限状态自动机。

几个术语

endpos集合,也称为为right集合,对于一个字符串S,设它的任意一个子串为s,则endpos[s]指s在S中所有出现位置的右端点集合。
trans边,和其它的自动机一样,是后缀自动机中的转移边。
suffix—link边,其实不是自动机上的边,但可以使算法更加强大。

形态

结点:因为一个字符串的子串个数是$O(n^2)$的,那么自动机上的结点实际上是一些等价类,后缀自动机把所有endpos集合相同的子串压缩成一个等价类,一个等价类就是自动机上的一个结点。

每个结点不会直接维护具体的字符串,而只是维护其中长度最长的子串的长度,对于一个结点u,称u代表的子串中长度最长的子串为$longest(u)$,有一个有趣的事实是,结点u所能代表的其它子串必定都是$longest(u)$的后缀,总结一下就是,每个结点代表的子串都是一段连续的字符串。

但并不是longest(u)的每个后缀都会与longest(u)在同一个结点里,因为可能某一个后缀会在其它地方多出现一次而导致endpos集合改变,我们把最早开始断开的那个longest(u)的后缀所在的结点称为fa(u),u到fa(u)实际上有一条边,就是suffix-link边。我们进一步观察,从u沿着suffix-link边一直向上跳,实际上就是在遍历longest(u)的所有后缀集合,后缀自动机把这些后缀压缩了。

性质

后缀自动机上任意两个结点所代表的endpos集合,要么是互为包含关系,要么必定完全不相交。

结点u的endpos集合只有两种可能,要么是u的所有儿子的endpos集合取并集,要么只比所有儿子的endpos集合并大1,并且这个大的1一定还是字符串的一个前缀。

所有suffix—link边构成了一个DAG,把它们反向就形成了后缀树。

设shortest(u)的长度为a,设longest(fa(u))的长度为b,那么有b+1=a,所以每个结点只维护能代表的子串的最长长度即可。

构建

后缀自动机的时空复杂度都是O(n)的,构造采用在线增量构造的方式。

假设我们已把1到i的字符都插入后缀自动机中了,那么在插入第i+1个字符c时,所需要的步骤应该是,先新建一个结点,因为至少1到i+1的这个串没有在原来的自动机里出现过。

设新建的这个结点为np,然后我们假设1到i这个串所在的结点为p,我们让p不断沿着suffix-link边向上跳。这样做是有道理的,因为当你插入一个字符c时,endpos集合会变化的子串实际只有原串的所有后缀拼接上字符c,所以我们沿着suufix-link向上跳实际是在压缩遍历原串的所有后缀。

当我们一直跳到根停下时,发现这条链上没有一个结点有c这个trans转移时,这说明自动机上其实都没有c这个字符,我们把np的fa设为1即可。只要还在向上跳,那中途遇到的所有结点都没有c这个转移,我们把遇到的这些结点的trans边连一条向np结点。但我们只要跳的过程中遇到一个结点p有转移c就必须要停止了,因为p的所有祖先必然都有c这个转移了。

设p读入c以后转移到的结点为q,我们定义len[p]为longest(p)的长度。这里需要讨论两类情况。第一,len[p]+1=len[q],这说明q结点代表的所有串都是新串的后缀,这时什么也不用做,只需把让fa(np)=q即可,因为q是suffix-link上遇到的第一个np的后缀。

第二,当len[p]+1不等于len[q]时,其实就是len[p]+1小于len[q]这种情况最为复杂的,这说明q结点里必然存在不是新串后缀的字符串,简单证明一下,如果此时q里的所有串都是新串后缀,说明q去掉一个c以后的结点必然还都是旧串的后缀,但是因为len[p]+1小于len[q],这说明这个结点一定不是p,但我们在跳的过程中并没有先遇到这个结点,说明这个结点不存在,于是可以证得q代表的字符串一定不全是新串的后缀。
其实应该是长度比len[p]+1大的子串不是新串的后缀,而其它串是新串的后缀,那我们在读入c以后,是新串后缀的那些串,它们的endpos集合就都多了一个,于是这个结点的子串它们的endpos集合不再全部相同了,于是我们需要新建立一个结点nq,nq的trans边和q的trans边是相同的,因为nq只是我们从q里拆出来的一个点,fa(nq)就是原来的fa(q),而把fa(q)设为nq,再把fa(np)设为nq,然后我们再继续在suffix——link链上向上跳,当遇到的结点有一个转移边c时指向q时,把这些结点的trans设为nq,理由是因为这些串的endpos必然都加了1。当结点的trans[p][c]不是q时,就不需要再向上了。
至此,后缀自动机的构造就完成了。

应用

判断一个串是不是另一个串的子串

直接在后缀自动机上跑,能跑完就是子串。

本质不同的子串个数

累加每个结点所能代表的子串个数就是答案。

字典序第K大的子串(相同的不同位置算多个)

先在suffix树上dp处理出每个结点的endpos集合的大小,然后再dp一次处理出f[i],f[i]代表从i结点开始向后走能到达的子串个数,最后我们在自动机上走一次,每次沿着字典序最小边转移,走过的路径就是答案。

两个串的最长公共子串

把一个串建立SAM,用另一个串在上面匹配,能走trans边就走,当发现不能匹配时,沿着suffix边向上跳即可。

扩展应用

维护多个串,利用广义后缀自动机,广义的SAM就是建立在Trie树上的SAM.
维护具体的endpos集合,使用线段树合并即可。

avatar Decaku 菜菜菜