【搬运】后缀自动机

前言

本文参考WC2012陈立杰论文,在其基础上作总结与扩展。

简介

后缀自动机(Suffix Automaton,下简称SAM),是可以识别字符串SS的所有后缀的有限状态自动机。它也可以用来识别字符串SS的所有子串,处理许多字符串的问题。

有限状态自动机

有限状态自动机是一种用于识别字符串的模型。

自动机由五个部分组成,alphaalpha:字符集,statestate:状态集合,initinit:初始状态,endend:结束状态集合,transtrans:状态转移函数。

对于自动机AA,若SendS\in end,则称AA能识别字符串SS,记A(S)=trueA(S)=true,否则A(S)=falseA(S)=false

trans(s,ch)trans(s,ch)表示当前状态ss,在读入字符chch之后,所到达的状态。

那么自动机识别一个字符串SS的过程是:从初始状态initinit开始,对SS的每个字符chch依次执行状态转移trans(cur,ch)trans(cur,ch),最终的状态tt就是SS所在的状态。

trans(init,S)trans(init,S)表示从initinit开始,在读入字符串SS之后,所到达的状态。

字符串SS的后缀自动机需要满足的,就是A(trans(init,str))=trueA(trans(init,str))=true当且仅当strstrSS的后缀,也就是A能且只能识别SS的后缀。

SAM与后缀树

事实上,SAM并没有那么抽象或遥不可及。我们熟悉的后缀树就是SAM最简单的实现。

对于字符串aabbabd,建立它的后缀树:

我们可以把它看成一个SAM:状态集合是树上所有点,初始状态是rootroot,状态转移函数是树的边,结束状态是叶子节点。因为后缀树的叶子节点表示的正是字符串的所有后缀,所以后缀树就是一个SAM。

但这样实现的问题在于:时空复杂度过大。尽管后缀树有各种优化,但优化的效果仍不理想,不能达到线性的复杂度,而且代码繁难。

最简状态自动机

最简状态自动机,是指状态数最少的自动机。

通过下文要讲的状态的合并,可以将SAM的状态数优化到O(n)O(n),得到最简状态SAM。我们平常使用的SAM,就是最简状态SAM。

SAM上的状态

在讲状态合并之前,首先要明确SAM上应该有哪些状态。

ST(str)=trans(init,str)ST(str)=trans(init,str),即从初始状态开始,读入字符串strstr后,所到达的状态。

记字符串SS的子串集合为Fac(S)Fac(S)

在刚才用后缀树实现的SAM上,状态集合是{ST(str)strFac(S)}\{ST(str)\mid str\in Fac(S)\},其实对于SAM的所有实现都是这样。

因为,SAM的功能是识别SS的所有后缀。则SAM上保留的状态,应该是所有有潜力成为后缀(即再读入几个字符就成为后缀)的子串。那么,就应该保留SS的后缀的所有前缀,即SS的所有子串Fac(S)Fac(S)

形式化地,ST(str)nullST(str)\neq null当且仅当strFac(S)str\in Fac(S)

此时,原串的每个子串对应着一个状态,这就使状态数具有O(n2)O(n^2)的数量级,这是非常不妙的。于是,我们来考虑一下如何对这些状态进行合并。

状态的合并

考虑一下,对于一个状态,我们关心什么。

SAM的最终目的是识别后缀。所以对于一个状态,我们唯一关心的是,它能够识别哪些串。

回顾一下识别的定义:ST(a)ST(a)能识别字符串bb,当且仅当abSufab\in Sufabab是字符串aabb连接,SufSuf是后缀集合)。

那么,可以得到bSufb\in Suf

aa在原串SS中出现的位置为{[l1,r1],[l2,r2],,[lk,rk]}\{[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\}。那么,ST(a)ST(a)能识别的字符串b{[r1+1,n],[r2+1,n],,[rk+1,n]}b\in\{[r_1+1,n],[r_2+1,n],\dots,[r_k+1,n]\}nnSS的长度)。

可以发现,可识别的串与ll无关,只与rr有关。换句话说,对于一个状态,我们只关心rr

重要定义Right(a)={r1,r2,,rk}Right(a)=\{r_1,r_2,\dots,r_k\}(即aaSS中出现位置的右端点集合)。

那么,对于一个状态,我们只需要关心RightRight集合即可。这就意味着:

RightRight集合相同的状态,都可以被合并成一个。

所以,一个状态ss,由所有RightRight集合是Right(s)Right(s)的字符串组成。

如此合并之后,状态数就大大减小了。事实上,状态数已经减小到了O(n)O(n)。至于证明,下面会提到。

状态对应的字符串

刚才说了,状态ss由所有RightRight集合是Right(s)Right(s)的字符串组成。那么,如何确定这些字符串呢?

rRight(s)r\in Right(s),事实上,只要给出串长度lenlen,就可以确定一个串[rlen+1,r][r-len+1,r]

对于状态ss,只有一些符合条件的lenlen,才能使得到的串str=[rlen+1,r]str=[r-len+1,r]属于状态ss,也就是使得Right(str)=Right(s)Right(str)=Right(s)

易证,若长度llrr都合法,那么len[l,r]len\in[l,r]都合法。也就是说,合法长度是一段区间。

一个定义:状态ss和合法长度区间记为[Min(s),Max(s)][Min(s),Max(s)]

Right集合之间的关系

结论:任意两个状态的RightRight集合,要么不相交,要么一个是另一个的真子集。

这个结论非常重要,是SAM可以达到线性复杂度的基础。

证明如下:

设两个状态为a,ba,bRightRight集合为Ra,RbR_a,R_b

RaR_aRbR_b相交,取rRaRbr\in R_a\cap R_b

由于a,ba,b对应的串不可能有交集,则[Min(a),Max(a)][Min(a),Max(a)][Min(b),Max(b)][Min(b),Max(b)]也不会有交集。不妨设Max(a)<Min(b)Max(a)<Min(b)

那么,由于都是从rr往前,而且aa中的串更短,则aa中所有串都是bb中所有串的后缀。

这就意味着,bb中的串出现的位置,aa中的串也必然出现了,即RbRaR_b\subseteq R_a

又因为两个状态RightRight集合不可能相同,则RbRaR_b\subsetneq R_a,结论得证。

parent树

从上述结论可以发现,RightRight集合构成了一个树形结构,我们称之为parent树。

那么,通过“父子真包含”和“兄弟不相交”这两个性质,容易证明结点个数为O(n)O(n),也就是说SAM的空间复杂度是线性的。

实际上,parent树上儿子与父亲的合法长度区间[Min(s),Max(s)][Min(s),Max(s)]也有着联系:

设状态ss在parent树上的父亲是fafass的合法长度区间为[Min(s),Max(s)][Min(s),Max(s)]

考虑长度Min(s)1Min(s)-1对应的串strstr,它不在状态ss中,说明随着串变短,出现的位置越来越多,Right(str)Right(str)已经超出了Right(s)Right(s)的范围,即Right(str)Right(str)包含Right(s)Right(s),而且是包含Right(s)Right(s)的集合中最小的一个。

根据parent树的定义,strstr一定属于状态fafa,那么Min(s)1<=Max(fa)Min(s)-1<=Max(fa)

又因为Right(s)Right(s)Right(fa)Right(fa)有交集,那么合法长度就不能有交集(不然会有同时处于两个状态的串)。所以Min(s)>Max(fa)Min(s)>Max(fa)

综上:Max(fa)=Min(s)1Max(fa)=Min(s)-1

Right集合的存储

SAM上的每个状态,都有一个对应的RightRight集合。如果暴力存储每个状态的RightRight集合,空间将是O(nlogn)O(n\log n)的。但如果利用我们利用parent树的一些性质,就可以不必直接存储每个结点的RightRight集合。

如果按照上面那张图,可以发现在parent树上,一个结点的RightRight集合是其所有子结点的RightRight集合的并集。

那么,一个结点的RightRight集合,就可以通过遍历其子树上的叶子节点得到,不必直接存储。

如果得到了某个串的RightRight集合大小,就可以求出它在原串中出现了几次,这是RightRight集合最经典的用法。当然这些都是后话。

错误纠正

(以下内容陈立杰论文中没有提到,不保证正确性,请带着批判的眼光阅读或跳过它也没有什么影响)。

回到这张图。这张图过于理想了,很容易误导人,使人感觉parent树的长相都这么好看。事实上,真正的parent树并不太可能长得这么可爱。

首先,Right集合里的元素并不一定是{1,2,3}\{1,2,3\}这样连续的,仍然存在{2,5,7}\{2,5,7\}这样的集合。

还有一点,就是刚才说的“在parent树上,一个结点的RightRight集合是其所有子结点的RightRight集合的并集。”这句话是错的。

以字符串aa为例,它有两个子串:a、aa,对应的RightRight集合分别为{1,2},{2}\{1,2\},\{2\}。而{1,2}\{1,2\}在parent树上有且只有{2}\{2\}这个子结点,元素11缺失了,显然不符合上述结论。

我们来分析一下“缺失元素”的本质。设当前状态为ss,缺失元素为rr

缺失元素rr,本质就是不存在RightRight集合为{r}\{r\}的串。这意味着什么呢?

我们假设存在RightRight集合为{r}\{r\}的状态,那么它一定是ss的儿子,我们把它记为sonson。根据前面说的parent树的性质,sonson状态的合法长度区间为[Max(s)+1,r][Max(s)+1,r]。而状态sonson不存在,说明Max(s)+1>rMax(s)+1>r。对于状态ss,显然有Max(s)<=rMax(s)<=r,于是可得:

状态ss缺失元素rr,当且仅当Max(s)=rMax(s)=r

由此,我们可以得到“缺失元素”这种情况的一个限制:对于状态ss,若其缺失元素,只会缺失Right(s)Right(s)中最小的rr

证明:

ss缺失两个或两个以上元素,则Max(s)=r1,Max(s)=r2,Max(s)=r_1,Max(s)=r_2,\dots相互矛盾。

ss缺失的元素不为最小,设缺失元素rr,最小元素为r0r_0。因为Max(s)=rMax(s)=r,而Max(s)r0Max(s)\le r_0,得到rr0r\le r_0,矛盾。

故:对于状态ss,若其缺失元素,只会缺失Right(s)Right(s)中最小的元素rr

所以,缺失元素并不会干扰我们之前的复杂度证明。若一个状态缺失元素rr,我们只要把缺失的{r}\{r\}人为补上,就可以得到理想的parent树,上面的证明仍然有效。而补的个数也是O(n)O(n)的。

至于RightRight集合的存储,就要做一些改动:

对于元素rr,若存在Right(a)={r}Right(a)=\{r\},则把元素rr放在aa上。否则,设状态bb缺失元素rr,则把元素rr放在bb上。求RightRight集合时,只要把子树上放的元素并起来即可。

例如字符串aa,只有状态{1,2}\{1,2\}{2}\{2\}。所以把元素11放在{1,2}\{1,2\}上,把元素22放在{2}\{2\}上。求RightRight时只要求子树上元素构成的集合即可。

线性构造算法

经历了艰难的理解过程,终于要进入正题了:SAM的线性构造算法。

在此之前,先明确一点:前文讲的parent树,和SAM的真实结构是两个东西。parent树只是用来辅助构造SAM的。

本文介绍的SAM构造算法是在线算法,也就是从左到右把字符串中的字符一个个加入SAM。


设当前串为TTTT的长度为LL,要加入的字符为xx

首先,考虑加入xx会影响哪些状态。

加入xx后,新增了若干个子串,这些子串都属于Suf(Tx)Suf(Tx)TxTx的后缀)。那么Suf(Tx)Suf(Tx)对应的状态都要被改动。

另外,考虑哪些串会转移到Suf(Tx)Suf(Tx):显然只有Suf(T)Suf(T)通过trans(x)trans(x)会转移到Suf(Tx)Suf(Tx)。所以Suf(T)Suf(T)对应的转移函数都需要修改。

于是得出结论:添加字符xx,需要改动的状态为Suf(T)Suf(T)Suf(Tx)Suf(Tx)。而Suf(Tx)Suf(Tx)可以通过trans(Suf(T),x)trans(Suf(T),x)得到。所以我们只需要枚举Suf(T)Suf(T)

Suf(T)Suf(T)对应的状态(即RightRight集合中包含LL的状态)为{v1,v2,,vk}\{v_1,v_2,\dots,v_k\}。那么,如何得到这些状态呢?

由于此时必定存在RightRight集合为{L}\{L\}的状态(串TT对应的状态),设这个状态为pp。那么由于parent树的性质,所有的vv都是pp的祖先,可以利用Parent函数(Parent(s)Parent(s)ss在parent树上的父亲)得到它们。

不妨把所有vv从后代到祖先排为v1=p,v2,,vk=rootv_1=p,v_2,\dots,v_k=root。另外,新建状态np=ST(Tx)np=ST(Tx),则Right(np)={L+1}Right(np)=\{L+1\}

下面要做的事情,就是把状态npnp插到SAM里去,并且修改ST(Suf(T))ST(Suf(T))(就是所有viv_i)的转移函数和ST(Suf(Tx))ST(Suf(Tx))(就是trans(vi,x)trans(v_i,x))的RightRight集合。


首先,从后代到祖先枚举viv_i

上文说过,我们需要修改viv_i的转移函数,也就是trans(vi,x)trans(v_i,x)

设当前枚举的vvRightRight集合为{r1,r2,,rk=L}\{r_1,r_2,\dots,r_k=L\}

考虑在后面添加字符xx,那么只有S[ri+1]=xS[r_i+1]=xrir_i满足要求。

trans(v,x)=nulltrans(v,x)=null,则说明vv中没有满足要求的rir_i

但随着v1,v2,v3,v_1,v_2,v_3,\dotsRightRight集合逐渐扩大,若viv_i中有满足要求的rr,则vi+1v_{i+1}中也有。

所以,trans(v,x)=nulltrans(v,x)=nullvv是从v1v_1开始连续的一段。

一个结论:添加完字符xx后,Right(trans(v,x))Right(trans(v,x))一定包含L+1L+1

因为根据定义,状态vv包含的其中一个串是TT的后缀,再添一个xx就变成了TxTx的后缀,对应的r=L+1r=L+1

所以,对于这些原本trans(v,x)=nulltrans(v,x)=nullvv,显然修改完的Right(trans(v,x))={L+1}Right(trans(v,x))=\{L+1\},也就是说trans(v,x)=nptrans(v,x)=np,直接连边即可。


处理完trans(vi,x)=nulltrans(v_i,x)=nullviv_i,我们枚举到了第一个trans(vi,x)nulltrans(v_i,x)\ne nullviv_i,称之为vpv_p

trans(vp,x)=qtrans(v_p,x)=q

添加完字符xx后,Right(trans(vp,x))Right(trans(v_p,x))一定包含L+1L+1,看似可以把L+1L+1直接插入Right(q)Right(q)。但其实并不能这样做,以下是反例:

(第一行是vpv_p,第二行是qq)。

可以看出,若把L+1L+1强行插入Right(q)Right(q),则Max(q)Max(q)r=L+1r=L+1的串所限只能取到Max(vp)+1=6Max(v_p)+1=6,而原来Max(q)=7Max(q)=7Max(q)Max(q)的缩短将会导致一系列问题,所以我们不能这么做。

(不过如果Max(q)Max(q)本来就等于Max(vp)+1Max(v_p)+1,则并不会出现什么问题。只需让Parent(np)=qParent(np)=q,相当于在Right(q)Right(q)中插入L+1L+1,就可以结束这个阶段了)。

此时,可以发现qq实际上被分成了两段:

(第一行是vpv_p,第二、三行是被分成两段的qq)。

于是,我们新建结点nqnq,使Right(nq)=Right(q){L+1}Right(nq)=Right(q)\cup\{L+1\}(对应图片第三行)。同时Max(nq)=Max(vp)+1Max(nq)=Max(v_p)+1

为什么Max(nq)=Max(vp)+1Max(nq)=Max(v_p)+1?有没有可能更大?

实际上,因为vpv_p的所有儿子都没有xx的转移边,这就说明比Max(vp)Max(v_p)更长的TT的后缀再接上一个字符xx都是没有在TT中出现过的,也就是说它们在添加x之后的RightRight集合一定是{L+1}\{L+1\},那么就不会在nqnq中。

先考虑np,q,nqnp,q,nq这些状态在parent树上的关系:

由于Right(q)Right(nq)Right(q)\subsetneqq Right(nq),则:Parent(q)=nqParent(q)=nq

同时Right(np)={L+1}Right(nq)Right(np)=\{L+1\}\subsetneqq Right(nq),则:Parent(np)=nqParent(np)=nq

最后,把Parent(nq)Parent(nq)设为原来的Parent(q)Parent(q)。为什么可以这么做?

因为qq表示的字符串中包含TxTx的后缀,设这个串为strstr,结束位置为rrParent(q)Parent(q)RightRight集合中肯定也包含rr,且从rr往前的串长度比qq短,这就意味着Parent(q)Parent(q)中包含strstr的后缀(strstr的后缀同时也是TxTx的后缀)。进而Right(Parent(q))Right(Parent(q))就包含L+1L+1

又因为Right(q)Right(Parent(q))Right(q)\subsetneqq Right(Parent(q)),则Right(nq)=Right(q){L+1}Right(Parent(q))Right(nq)=Right(q)\cup \{L+1\}\subsetneqq Right(Parent(q)),即:Parent(nq)=Parent(q)Parent(nq)=Parent(q)

总结步骤:Parent(q)=Parent(np)=nqParent(q)=Parent(np)=nqParent(nq)=Parent(q)Parent(nq)=原来的Parent(q)

处理完ParentParent树上的连边,还要考虑SAM上的连边,也就是转移函数。

注意到在trans(nq,ch)trans(nq,ch)中,nqnq相比起qq多的结束位置L+1L+1是不起作用的(已经到末尾了没法再添字符)。所以nqnq的转移函数直接从qq拷贝过来即可。


处理完vpv_p,剩下的vp+1,,vkv_{p+1},\dots, v_ktrans(x)trans(x)一定都不为空。并且,随着Right(v)Right(v)的变大,Right(trans(v,x))Right(trans(v,x))也会变大。那么只有一段vp,,vev_p,\dots,v_etrans(v,x)=qtrans(v,x)=q。因为qq已经被我们拆成了qqnqnq,且nqnq包含{L+1}\{L+1\},那么就应该把vp,,vev_p,\dots,v_etrans(v,x)trans(v,x)都改为nqnq

至于vev_e以后的vv,就不用改动了。你可能会问,不应该在剩下的trans(vi,x)trans(v_i,x)的Right集合中插入{L+1}\{L+1\}吗?

事实上,剩下的viv_itrans(vi,x)trans(v_i,x)一定是nqnq的祖先,而刚才nqnq中已经加入了L+1L+1,则trans(vi,x)trans(v_i,x)中就也加入了L+1L+1,无需再改。

至此,算法结束。

步骤总结

设已经加入的串为TT,长度为LL,当前待添加字符为xx

p=ST(T)p=ST(T),即RightRight集合为{L}\{L\}的状态。

新建np=ST(Tx)np=ST(Tx),即RightRight集合为{L+1}\{L+1\}的状态。

pp的所有trans(v,x)=nulltrans(v,x)=null的祖先vvtrans(v,x)=nptrans(v,x)=np

pp的第一个trans(v,x)!=nulltrans(v,x)!=null的祖先为vpv_p。若找不到这样的vpv_pParent(np)=rootParent(np)=root并退出。

q=trans(vp,x)q=trans(v_p,x)。若Max(q)=Max(vp)+1Max(q)=Max(v_p)+1,则Parent(np)=qParent(np)=q并退出。

否则,新建结点nqnqParent(q)=Parent(np)=nqParent(q)=Parent(np)=nqParent(nq)=Parent(q)Parent(nq)=原来的Parent(q),并且nqnq的转移函数拷贝qq的。

对于所有为pp的祖先且满足trans(v,x)=qtrans(v,x)=q的状态vvtrans(v,x)=nqtrans(v,x)=nq

代码

SAM主要难在理解,代码其实非常短。

1
2
3
4
5
6
7
8
9
10
11
12
void Extend(char c) {
int x = c - 'a', p = last, np = last = ++top;
mx[np] = mx[p] + 1; cnt[np] = 1;
for (; p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
if (!p) { fa[np] = 1; return; }
int q = ch[p][x];
if (mx[q] == mx[p] + 1) { fa[np] = q; return; }
int nq = ++top; mx[nq] = mx[p] + 1;
fa[nq] = fa[q]; fa[q] = fa[np] = nq;
memcpy(ch[nq], ch[q], sizeof(ch[q]));
for (; ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
}

代码中mx[]存储Max(s)Max(s),fa[]存储Parent(s)Parent(s),cnt[]用来计算RightRight集合大小(构造完SAM后统计一下子树cnt之和即为RightRight集合大小)。

不存Min(s)Min(s),是因为Min(s)=Max(fa)+1Min(s)=Max(fa)+1,不需要单独存。

其它部分就跟上面说的步骤差不多了。

后记

终于把论文抄完了……orzclj。


【搬运】后缀自动机
https://www.d0j1a1701.cc/p/c4eb2e38/
作者
王小花
发布于
2022年8月20日
许可协议
CC-BY-SA