Steven_MengのBlog

后缀自动机

回顾

我们来复习一下 DFA (确定有限状态自动机)的定义:

  1. 字符集 $\Sigma $ ,自动机只能输入这些字符,对于小写英文字符串,$\Sigma = \texttt{abcd…z}$,对于 01 字符串,$\Sigma = \texttt{01}$ 。

  2. 状态集合 $Q$ ,如果我们把 DFA 看成一张图,$Q$ 就是图上所有节点组成的集合。

    在下面的论证过程中,可能不分“节点”和“状态”,其实他们是一样的。

  3. 起始状态 $start$ ,$start \in Q$ (注意$start$ 只有一个节点),就是开始的节点。

  4. 接受状态集合 $F$ ,$F \subseteq Q$,是一些特殊的节点,当我们把字符串输入这个自动机,经过一系列的转移,最终达到这些节点,我们称这个字符串是可以接受的。

  5. 转移函数 $\delta$ ,$\delta$ 是一个接受两个参数返回一个值的函数,第一个参数和返回值都是一个状态(节点),第二个参数是字符集里面 的一个字符,如果我们把 DFA 看成一张图,那么这个函数可以写成下列的形式 $\delta(u,c)=v$ ,其中 $u,v$ 都是节点,$c$ 是一个字符,定义 $\delta(u,s)=\delta(\delta(\delta(u,s[1]),s[2]),s[3]…)$。

注意,如果状态 $u$ 没有 $c$ 的转移,记 $\delta(u,c)=null$。规定 $\delta(null,c)=null$。

定义把一个字符串 $s$ 按顺序输入 DFA $A$ ,能不能被 $A$ 接受,结果为 $A(s)$,为真(True)或假(False)。

我们定义,一个字符串的后缀自动机(SAM)是一个接受且 仅接受 这个字符串的所有后缀的 DFA,我们记字符串 $s$ 的后缀自动机为 $SAM_s$ ,定义 $SAM_s$ 转移函数为 $\delta_s$ 。

那么,一个字符串 $t$ 是字符串 $s$ 的后缀,当且仅当 $SAM_s(t)=True$。

还有,一个字符串 $t$ 是字符串 $s$ 的子串,当且仅当 $\forall \delta_s(start_s,t) \not= null$。

朴素 SAM

可以将一个字符串的所有后缀插入一个 Trie 里面构建 DFA,我们称这样的 DFA 为朴素 SAM。

比如字符串 abaaabaa 的朴素 SAM 为:

这样,节点的数量和构建 SAM 的复杂度都为 $\mathcal O(n^2)$ 的,考虑怎么优化?

我们可以优化成 最简 SAM ,可以将节点数量和时间复杂度都降到 $\mathcal O(n)$ 。

最简 SAM

right 集合

以下字符串的下标都从 0 开始。

定义

对于一个字符串 $t$ 它在 $s$ 中出现的位置集合为:$\lbrace [l_1,r_1),[l_2,r_2),\cdots,[l_n,r_n)\rbrace$。

我们定义 $right(t)$ 为 $\lbrace r_1,r_2,\cdots,r_n\rbrace$。

right 集合等价类

定义

right 集合相等的字符串,构成一个 right 集合等价类。

对于串 abaaaba,right 集合为 $\lbrace 4,8 \rbrace$ 的字符串为 $\lbrace \texttt{abaa},\texttt{baa}\rbrace$ ,这两个字符串构成一个 right 集合等价类。

right 集合等价类和最简​ SAM 有什么关系?

我们定义 $reg(v)$ 表示从状态 $v$ 开始能识别的字符串集合,即 $t \in reg(v)$ 当且仅当 $\delta (v,t)\in F$。

因为 SAM 是一个 DAG ,所以 reg​ 集合的大小是有限的。

我们找出字符串 $t$ 的 right 集合 $right(t)$ ,我们发现在 $t$ 后面补上一个字符串 $s[r_i..n]$ ,就得到了一个 $s$ 的后缀。所以若 $right(t_1)=right(t_2)$ ,那么 $reg(\delta(start,t_1))=reg(\delta(start,t_2))$,同时,反着推结论也是成立的。

我们发现,right 集合等价,能推出 reg 集合等价,于是想到,可以 将 right 集合相同的字符串压成一个节点

这样,我们还可以推出 SAM 状态最少,因为 SAM 上节点两两的 reg 集合互不相同。

字符串 abaaabaa 的最简 SAM:

由于字符串和节点是等价的,我们定义 $right(v)$ 为节点 $v$ 代表的字符串的 right 集合。

right 集合等价类的性质

我们定义,对于每个状态 $v$ ,$max(v)$ 和 $min(v)$ 分别表示这个状态对应的最长和最短的字符串。

具体来说:

$max(v)=maxlen(\forall s,\delta(start,s)=v)$。

$min(v)=minlen(\forall s,\delta(start,s)=v)$。

其中,$maxlen,minlen$ 分别代表从字符串集合中选出最长和最短的字符串。

  1. $v$ 对应的任意一个字符串都是 $max(v)$ 的后缀,由于 $v$ 对应的任意一个字符串都属于 right 集合等价类,他们对应的 $r_i$ 也是相同的。我们观察 $\lbrace [l_1,r_1),[l_2,r_2),\cdots,[l_n,r_n)\rbrace$,和$\lbrace [l_1’,r_1),[l_2’,r_2),\cdots,[l_n’,r_n)\rbrace$ ,显然,由于 $l_i$ 已经最小了,那么 $s[l_i’,r_i)$ 是 $s[l_i,r_i)$ 的后缀。

  2. $v$ 对应的任意一个字符串都不是 $min(v)$ 的真后缀。证明方法类似于 1. ,不再赘述。

  3. $v$ 包含所有这样的字符串,即,$v$ 包含所有长度在 $[len(min(v)),len(max(v))]$ 之间的字符串。

    要证 3. ,我们需再证一个引理,对于一个字符串 $t$ ,它的 right 集合是它的任意一个后缀的 right 集合的子集,这个很好证明,口胡一下,完整是字符串 $t$ 对前缀的限制较多,然而满足此处的字符串为 $t$ ,一定满足后缀为这个后缀。证明完了。

    根据这个引理,我们可以这样证明这个定理,对于一个位置 $p$ ,$right(s[i..p-1]) \subseteq right(s[i+1..p-1]) \subseteq \cdots $,然而 $right(min(v))=right(max(v))$,既然两边的集合互相相等,那么中间的一定相等。

    举个例子加深印象,对于字符串 abaaabaa ,它的 right 集合为 $\lbrace 6 \rbrace$ 的子串为 $\lbrace \texttt{aab}, \texttt{aaab}, \texttt{baaab}, \texttt{abaaab} \rbrace$,包含了所有长度处于 $[3,6]$ 之间、右端点为 5 的子串。

    我们再研究一下 $right(\texttt{ab}),right(\texttt{b})$,发现它们都等于 $\lbrace 2,6\rbrace$。

    如果我们能找到 right 集合开始不相等的地方,也就是所说的“分割点”,那么上述的“压缩”就变得可行了。

如何找到所谓的“分割点”?

parent 的概念

我们引入 parent 的概念。

定义一

延续刚才的思路,定义对于每个节点 $v$(除了 $start$),找到一个最长的字符串 $t$ 对应的状态 $u$,使得 $right(v)\subsetneq right(u)$ 。(注意是真子集,也就是 $right(v) \not= right(u)$)

定义 $parent(v)=u$。

定义二

对于每个状态 $v$ (除了起始状态),$min(v)$ 字符串去掉开头字符对应的状态,就是 $parent(v)$。

对于字符串 abaaabaa ,$parent(\delta(start,\texttt{aab}))=parent(\delta(start,\texttt{aaab}))=\delta(start,\texttt{ab})=\delta(start,\texttt{b})$。

显然,有 $len(min(v))=len(max(parent(v)))+1$。

parent 树

我们可以发现,right 集合要么包含,要么不相交,parent 集合可以看成 right 集合的包含关系构成是树。

还是串 abaaabaa:

(第二张图左边没显示出来)

最简 SAM 的线性构造

例题

 评论