后缀数组(SA)和后缀自动机(SAM)详解

2018-04-16jzqjzq?

字符串题目嘛……
大致有模式串匹配问题,hash,还有后缀数据结构啦
后缀数据结构也很多啦……不过用得多的就这两种(其实后缀树用处也不少吧)
其实我怕ZJOIDay2又考字符串题才再开个坑
先开坑

后缀数组(SA)

因为这个东西之前我会……所以不多解释
关键词:SA,rank,Height数组

说实话……SA大多数情况下只有Height有用……
这东西没有前置技能

定义

首先定义几个东西
对于串$S$的所有后缀$Suf[i]$进行后缀排序
对于后缀$Suf[i]$(表示从$i$到$length(S)$的后缀),定义$Rank[i]$表示这个后缀在整个后缀排序中的排名
对于一个排序后的字符串集,定义$SA[i]$表示排名为$i$的后缀对应原串的起始位置
假设我们已经求出了$Rank$和$SA$两个数组(具体怎么构造稍后细讲),
于是定义$Height[i]$表示排名为$i$的后缀与排名为$i-1$的后缀的$lcp$(最长公共前缀)

构造Height

我们先来说$Height$怎么求
求出$Rank$和$SA$之后,我们考虑从$Height[i-1]$推向$Height[i]$
有一个结论:
$$Height[i]>=height[i-1]-1$$
证明略(这个结论冷静分析一下应该就能发现
有了这个之后,我们继承上次的$Height$,然后直接暴算,复杂度是$O(n)$
代码如下:

1
2
3
4
5
6
7
inline void build_height(){
for(int i=1,k=0;i<=n;i++){
int j=sa[rank[i]-1];if(k)k--;
for(;s[i+k]==s[j+k];k++);
height[rk[i]]=k;
}
}//Height

构造SA和Rank

好说完$Height$怎么求之后,我们说说怎么求$SA和Rank$数组
目前我已知的求法有以下两种

倍增

不断进行双关键字后缀排序
对于第i次排序,对于位置$j$,我们把$Rank[j]和Rank[j+2^{i-1}]$拿出来,进行双关键字排序
总共需要$log$次排序过程
类似以下的过程

使用基数排序就可以把总复杂度做到$O(nlogn)$
这是求出$SA$和$Rank$的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void build_sa(){
for(int i=1;i<=n;i++){
rank[i]=s[i];ss[i]=i;
}
//ss是一个辅助数组
m=200;Sort();
for(int i=1,p=1;p<n;m=p,i<<=1){
p=0;for(int j=n-i+1;j<=n;j++)ss[++p]=j;
for(int j=1;j<=n;j++)if(sa[j]>i)ss[++p]=sa[j]-i;
Sort();swap(rk,ss);
rank[sa[1]]=p=1;
for(int j=2;j<=n;j++){
if(ss[sa[j]]!=ss[sa[j-1]]||ss[sa[j]+i]!=ss[sa[j-1]+i])p++;
rank[sa[j]]=p;
}
}
}//sa,rk

这是基数排序的代码:

1
2
3
4
5
6
7
inline void Sort(){
for(int i=0;i<=m;i++)tong[i]=0;
for(int i=1;i<=n;i++)tong[rank[ss[i]]]++;
for(int i=1;i<=m;i++)tong[i]+=tong[i-1];
for(int i=n;i;i--)sa[tong[rank[ss[i]]]--]=ss[i];
}
//tong就是基数排序用的桶……

DC3

理论复杂度$O(n)$,然而这个东西的常数极大加上代码实现困难,这里不再赘述
说实话这东西常数应该已经大到和倍增没啥区别吧(最多快2倍)……
有兴趣的可以百度或者Google一下辣~

应用

最后来说一下SA的实际应用吧
首先,对于串$S$中的两个后缀$Suf[i]和Suf[j]$,两者的$lcp$是
$min(Height[min(Rank[i],Rank[j])+1]…Height[max(Rank[i],Rank[j])])$
证明很显然……
这个东西就可以解决一些子串$lcp$问题
然后SA还可以去做很多子串计数类问题,重复子串问题等等
看起来还是很有用的……

后缀自动机(SAM)

可以这么说……我们完全可以用SAM直接构造SA……
关键词:DFA,right集合,parent树,trans转移数组

缓更……
这是一种极其巧妙的数据结构,可以识别字符串s所有的后缀,并且它的节点中包含且仅包含了S所有的子串

前置技能(DFA)

首先关于DFA(确定性有限状态自动机),这个……
只要知道SAM是DFA就行了吧……
定义:

一个确定性有限状态自动机是一堆“零件”的集合,可以“识别”一些字符串
标准的定义是一个由(Q, Σ, δ, q0, F)构成的5元组,但是这里并不讲解正规定义

如果实用一点来讲的话,DFA是一张图,有一个开始节点,代表空串,有一堆点,各个点并没有实际意义(准确来讲部分自动机,但是不是所有的自动机都要求节点有意义),点之间有边。
和普通的图区别最大的一点就是,DFA的图的边是有实际意义的,一条边代表了一种字符,一个点必须有且仅有每一个字符的出边(如果某个出边无意义,一般的做法是这个出边指向NULL节点)
那么我们发现,如果从起点出发,走出一条路径(随便走,并不要求简单路径),那么这个路径可以代表一个字符串。

定义一个字符串可以被一个DFA“识别”就是我们从初始点出发,走出这个字符串(显然这个路径必须是存在且唯一的,因为每个节点的某种类型的出边有且仅有一条)之后,我们到达了某些我们指定的节点上,那么就认为这个节点可以被这个自动机识别,另外这些节点在某些博客中被称为“接受节点”

接下来进入正题

这东西长啥样?

比如对于字符串aabbabd,它的SAM长这样:

定义

定义集合$Right$表示某串在母串S中出现的结束位置集合
比如说上图中子串ab的$Right$集合为${3,6}$
然后SAM的一个很nb的方法是把所有$Right$集合相同的串合并到一个点
这些点对应上图中的那些节点
然后这东西就很有用了
定义$dist[i]$表示$Right$集合编号为i的子串集合中最大的长度
定义$trans[i][k]$表示从i号点通过转移边字符为k到达的节点
显然$trans$对应了上图中蓝边的部分
那么上图中的绿边是什么?稍后细讲。因为这个东西很有用

Right集合的一些性质

$Right$集合有一些神奇的性质

  1. 同一$Right$集合内的串互为后缀
    这里的“互为后缀”是什么意思呢?就是长度小的那些串一定是长度大的串的后缀
    这个结论应该蛮显然……
  2. 同一$Right$集合内的串长度连续
    其实从性质1就可以推出来了……
    考虑子串s1,s2,如果它们属于一个$Right$集合,且$length(s1)>length(s2+1)$,那么夹在它们中间的那个子串显然$Right$集合也是相同的……
  3. 对于任意两个$Right$集合,两者的关系只可能是包含或无交集
    也蛮显然的吧……
    考虑两个$Right$集合有交集但不包含,那就是说两个集合中有相同的结束位置
    那么显然有一个集合中的串能够匹配到另外一个集合中的所有位置(自己意会一下),这样就矛盾了,于是结论成立

有了这些性质之后我们就可以应用那些绿边了
定义$parent[i]$或$fa[i]$表示满足$Right[i]\subseteq Right[fa[i]]$的最小集合
这个东西就对应了上图中的绿边
然后显然$parent$边组成了一棵$parent$树
其实这个东西就是反串的后缀树……不过我还没有明白如何直接转换……
虽然这并不是SAM的具体组成部分,但是对构造SAM非常有用!

构造

废话不多说,直接讲对于一个串S怎么构造出一个SAM
这个东西叫增量法
首先我们定义根对应的$Right$集合是所有结束位置(包括0),表示空串
然后我们考虑对S从前往后插入字符,我们设这个新字符为k
我们想啊,在串后面新加一个字符,等于原串的所有后缀加上这个字符
所以对于一个新的字符,我们新建一个节点$np$,设$dist[np]=dist[last]+1$
然后我们从上次新建的那个节点(不是等会要说的那个附加节点)开始,根据$parent$的一些性质,我们直接向$parent$跳上去
如果到达一个节点i,$trans[i][k]=null$,那么就修改为$np$并继续向上跳
如果碰到$trans[i][k]$有值的情况,我们要分类讨论了
如果$dist[trans[i][k]]==dist[i]+1$,那么说明这个转移边是有用的,我们直接把$parent[np]$设成$trans[i][k]$
否则说明这个边已经没有时效性了
那么我们新建一个点$nq$,把$trans[i][k]$的所有数据复制到$nq$,设$dist[nq]=dist[i]+1$
然后把$trans[i][k]和np$的$parent$全部改为$nq$即可
代码大致长这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct SAM{
int trans[2*N][30],fa[2*N],dist[2*N];
int cnt=0,rt,la;ll sz[2*N];
char s[N];
inline void extend(int x){
int v=s[x]-'a',p=la,np=++cnt;sz[np]=1;
la=np;dist[np]=x;
for(;p&&trans[p][v]==0;p=fa[p])trans[p][v]=np;
if(!p)fa[np]=rt;
else{
int q=trans[p][v];
if(dist[q]==dist[p]+1)fa[np]=q;
else{
int nq=++cnt;dist[nq]=dist[p]+1;
memcpy(trans[nq],trans[q],sizeof trans[q]);
fa[nq]=fa[q];fa[np]=fa[q]=nq;
for(;trans[p][v]==q;p=fa[p])trans[p][v]=nq;
}
}
}
inline void build(){
la=rt=++cnt;
scanf("%s",s+1);int l=strlen(s+1);
for(int i=1;i<=l;i++)extend(i);
}
}S;

这个东西的复杂度被clj大神证明为均摊$O(n)$,十分优秀

应用

一个很简单的应用:求一个串的不同子串个数
答案即为每个$Right$集合所含子串个数之和
对于$Right[i]$所含子串个数即为$dist[i]-dist[fa[i]]$,由上性质可以直接推出
求$Right[i]$大小(结束位置个数)可以用parent树得到
详见hihoCoder 后缀自动机三·重复旋律6
这个东西也可以去做很多题目
更多的应用将持续更新