后缀自动机学习笔记

写在前面

推荐hihocoder上的讲解,可以说是十分清楚了。

用好后缀自动机不是十分容易,但看完本文的总结应该能至少达到签到水平…


正文

后缀自动机(Suffix Automaton,简称SAM)。对于一个字符串S,它对应的后缀自动机是一个最小的确定有限状态自动机(DFA),接受且只接受S的后缀。

先给出一张图和一个表格。

对于字符串STR=“aabbabd”,它的后缀自动机是:

状态 子串 endpos
S 空串 {0,1,2,3,4,5,6}
1 a {1,2,5}
2 aa {2}
3 aab {3}
4 aabb,abb,bb {4}
5 b {3,4,6}
6 aabba,abba,bba,ba {5}
7 aabbab,abbab,bbab,bab {6}
8 ab {3,6}
9 aabbabd,abbabd,bbabd,babd,abd,bd,d {7}

接下来从状态(State)、转移函数(Transition Function)、后缀链接(Suffix Link)三个方面全方位了解一下后缀自动机的性质。

状态:

记号:

  • length(s)length(s)表示字符串 ss 的长度。
  • endpos(s)endpos(s)表示字符串 ssSTRSTR 中所有出现的结束位置集合。
  • substrings(st)substrings(st)表示状态 stst 中包含的所有子串的集合。
  • longest(st)longest(st)表示状态 stst 包含的最长的子串,shortest(st)shortest(st)表示 stst 包含的最短的子串。
  • maxlen(st)=length(longest(st))maxlen(st)=length(longest(st))

性质:

  • 从起始状态 SS 出发,沿着图中蓝线转移,对于 STRSTR 的子串最终会到达一个合法状态,不是子串的话最终会无路可走。
  • 对于 STRSTR 的两个子串 s1s_1s2s_2,不妨设length(s1)length(s2)length(s_1) \leq length(s_2)s1s_1s2s_2 的后缀当且仅当endpos(s2)endpos(s1)endpos(s_2) \subseteq endpos(s_1)s1s_1不是s2s_2的后缀当且仅当endpos(s1)endpos(s2)=endpos(s_1) \bigcap endpos(s_2) = \emptyset
  • 对于一个后缀自动机的状态 ststsubstrings(st)substrings(st) 里的字符串 endposendpos 集都相同,或者说同一个状态下的字符串构成了一个等价类,这样记 endpos(st)endpos(st) 表示该状态的 endposendpos 集。
  • 对于一个后缀自动机的状态 stst,以及任意 ssubstrings(st)s \in substrings(st),都有 sslongest(st)longest(st) 的后缀。
  • 对于一个状态 stst,以及任意的 longest(st)longest(st) 的后缀 ss,如果 ss 的长度满足:length(shortest(st))length(s)length(longsest(st))length(shortest(st)) \leq length(s) \leq length(longsest(st)),那么 ssubstrings(st)s \in substrings(st)
  • 换句话说,substrings(st)substrings(st) 包含的是 longest(st)longest(st) 的一系列连续后缀。

转移函数:

  • 记字符集合next(st)next(st)表示对于一个状态 stst ,从它开始下一个遇到的字符可能有哪些,形式化的写出来,有 next(st)=STR[i+1]iendpos(st)next(st) = {STR[i+1] \mid i \in endpos(st)} 。对于一个状态 stst 来说和一个next(st)next(st)中的字符c,你会发现substrings(st)substrings(st)中的所有子串后面接上一个字符c之后,新的子串仍然都属于同一个状态。比如对于状态4,next(4)=anext(4)={a},aabb,abb,bb后面接上字符a得到aabba,abba,bba,这些子串都属于状态6。
  • 定义转移函数 trans(st,c)=xlongest(st)+csubstrings(x)trans(st, c) = x \mid longest(st) + c \in substrings(x) 。换句话说,我们在longest(st)longest(st) 后面接上一个字符c得到一个新的子串 ss (随便哪个子串都会得到相同的结果),找到包含 ss 的状态 xx,那么 trans(st,c)trans(st, c) 就等于xx
  • 对应图中蓝线,比如 trans(4,a)=6trans(4, a)=6

后缀链接:

  • 前面我们讲到substrings(st)substrings(st)包含的是longest(st)longest(st)的一系列连续后缀。这连续的后缀在某个地方会“断掉”。比如状态7,包含的子串依次是aabbab,abbab,bbab,bab。按照连续的规律下一个子串应该是“ab”,但是“ab”没在状态7里,这是因为串变短了,就有可能在别的地方也会出现,即endposendpos集合大小变大了。比如aabbab,abbab,bbab,bab(状态7)的endposendpos集为{6},而“ab”(状态8)的endposendpos集为{3,6},“b”(状态5)的endposendpos集为{3,4,6}。
  • 于是我们可以发现一条状态序列:7->8->5->S。这个序列的意义是 longest(7)longest(7) 即aabbab的后缀依次在状态7、8、5、S中。我们用Suffix Link这一串状态链接起来,这条link就是上图中的绿色虚线。
  • 后缀链接组成了一棵以S为根的树。

构造后缀自动机:

构造比较复杂,还是推荐看 http://hihocoder.com/contest/hiho128/problem/1

具体改天再写~

时间复杂度 O(N)O(N) ,空间上状态数不超过 2N2N

代码中 son 表示转移函数,pre 表示后缀链接,cnt 表示 endposendpos 集合大小。

添加字符的过程中只能标出 endposendpos 大小为 11 的那些状态,需要对后缀链接构成的树形结构从叶子开始做拓扑排序,得到所有状态的 endposendpos 集合大小。

代码:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
struct SAM
{
int tot,last;
int son[N<<1][26],maxlen[N<<1],pre[N<<1];
int cnt[N<<1],in[N<<1],q[N<<1];
void init()
{
tot=0;
last=newnode();
}
int newnode()
{
++tot;
memset(son[tot],0,sizeof(son[tot]));
maxlen[tot]=pre[tot]=cnt[tot]=in[tot]=0;
return tot;
}
void add(int c)
{
int now=newnode();
maxlen[now]=maxlen[last]+1;
cnt[now]=1;
while(last && son[last][c]==0)
son[last][c]=now,last=pre[last];
if(last)
{
int x=son[last][c];
if(maxlen[x]==maxlen[last]+1) pre[now]=x;
else
{
int nq=newnode();
maxlen[nq]=maxlen[last]+1;
memcpy(son[nq],son[x],sizeof(son[x]));
pre[nq]=pre[x];
pre[x]=pre[now]=nq;
while(last && son[last][c]==x)
son[last][c]=nq,last=pre[last];
}
}
else pre[now]=1;
last=now;
}
void endpos()
{
int l=0,r=0;
for(int i=1;i<=tot;++i) ++in[pre[i]];
for(int i=1;i<=tot;++i)
if(!in[i])
q[r++]=i;
while(l!=r)
{
int x=q[l++];
if(pre[x]==0) continue;
cnt[pre[x]]+=cnt[x];
if((--in[pre[x]])==0)
q[r++]=pre[x];
}
}
} sam;
char s[N];
int main()
{
sam.init();
scanf("%s",s);
for(int i=0;s[i];++i) sam.add(s[i]-'a');
sam.endpos();
}

广义后缀自动机

解决多个串的问题,做法很简单,只需要添加每个串前让last=1即可,或者也可以对trie树建后缀自动机,则新加点时last为trie上的父节点。分析与证明在2015年国家集训队论文里有。

如果要记录一些信息,比如strval表示每个状态里的子串在多少个串中出现过,需要额外加一个lc维护该状态上一次出现是哪个串,每次沿着Parent向上更新出现次数,遇到lc=当前串的就停止。时间复杂度还不太会分析,待补。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void add(int id,int c)//id表示第几个串,编号从1开始
{
int now=newnode();
maxlen[now]=maxlen[last]+1;
cnt[now]=1;
while(last && son[last][c]==0)
son[last][c]=now,last=pre[last];
if(last)
{
int x=son[last][c];
if(maxlen[x]==maxlen[last]+1) pre[now]=x;
else
{
int nq=newnode();
maxlen[nq]=maxlen[last]+1;
memcpy(son[nq],son[x],sizeof(son[x]));
pre[nq]=pre[x];
lc[nq]=lc[x];strval[nq]=strval[x];//额外的信息
pre[x]=pre[now]=nq;
while(last && son[last][c]==x)
son[last][c]=nq,last=pre[last];
}
}
else pre[now]=1;
last=now;
//广义后缀自动机
while(now && lc[now]!=id)
{
lc[now]=id;
++strval[now];
now=pre[now];
}
}

//main

sam.init();
for(int i=1;i<=n;++i)
{
sam.last=1;
scanf("%s",s);
for(int j=0;s[j];++j) sam.add(i,s[j]-'a');
}

练习题目:

1.hihocoder #1445 : 后缀自动机二·重复旋律5

求字符串本质不同子串的个数,直接累加substrings(st)\left|substrings(st) \right|,利用maxlen数组及suffix link不难得出。

1
2
3
4
5
6
7
ll count()
{
ll ans=0;
for(int i=1;i<=tot;++i)
ans+=maxlen[i]-maxlen[pre[i]];
return ans;
}

2.spoj1811 LCS

求两个串最长公共子串,对一个串建后缀自动机,另一个串在上面走,如果当前状态没有当前字符的转移,就沿着suffix link往回跳,很好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int LCS(char *s)
{
int now=1,len=0,ans=0;
for(int i=0;s[i];++i)
{
int x=s[i]-'a';
if(son[now][x])
++len,now=son[now][x];
else
{
while(now && son[now][x]==0) now=pre[now];
if(now==0) len=0,now=1;
else len=maxlen[now]+1,now=son[now][x];
}
ans=max(ans,len);
}
return ans;
}

3.[bzoj3998: TJOI2015]弦论

求一个串的第K小子串T==0 表示不同位置的相同子串算作一个,T==1 则表示不同位置的相同子串算作多个。

还是先计算 endposendpos 集合大小cnt,如果 T==0,则每个状态cnt值都是1,如果 T==1,则还是和之前的代码一样,在suffix link构成的树上做拓扑排序,转移出cnt。

另外还需要知道从每个状态往后走会有多少种子串,记为 Sum[x]Sum[x],还是用同样的拓扑序转移

Sum[x]=cnt[x]+i=025Sum[son[x][i]]Sum[x]=cnt[x]+\sum_{i=0}^{25} Sum[son[x][i]]

然后从根开始按照字典序dfs一下就可以求出第K小子串了。

4.[bzoj3238: AHOI2013]差异

给一个字符串S,求1i<jnlen(Ti)+len(Tj)2lcp(Ti,Tj)\sum_{1\le i<j\le n} len(T_i)+len(T_j)-2lcp(T_i,T_j),其中 TiT_i 表示 ii 开始的后缀,lcplcp 表示最长公共前缀。

把原串倒过来建后缀自动机,这样就把前缀变成了后缀。两个前缀的最长公共后缀是对应后缀自动机上两结点的LCA ,实上统计的话,枚举LCA做类似树dp的事情数一数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void addedge()
{
for(int i=2;i<=tot;++i)
e[pre[i]].push_back(i);
}
void dfs(int x)
{
ll now=0;
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
dfs(y);
ans-=2LL*now*cnt[y]*maxlen[x];
now+=cnt[y];
}
if(cnt[x]==1) ans-=2*now*maxlen[x];
cnt[x]+=now;
}

或者这样,类似容斥一下的统计

1
2
3
4
5
6
7
8
9
10
void dfs(int x)
{
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
dfs(y);
cnt[x]+=cnt[y];
}
if(x!=1) ans-=1LL*cnt[x]*(cnt[x]-1)*(maxlen[x]-maxlen[pre[x]]);
}

5.是男人就过 8 题–Pony.AI A String Game

Alice和Bob玩游戏,有 nn 个串SiS_i,保证都是 tt 的子串,每人轮流从 nn 个串中取出一个串,并在结尾添加一个字符后放回去,要求是添加字符之后也要保证该串是 tt 的子串,无法操作的人输,Alice先手,问谁赢。

显然是要在 tt 的后缀自动机上博弈,要注意不能直接从根开始dfs,需要先做搞出拓扑序。

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
27
28
29
30
31
32
33
34
35
int calc(char *s,int n)
{
int now=1;
for(int i=0;i<n;++i)
now=son[now][s[i]-'a'];
return ans[now];
}
void work()
{
for(int i=1;i<=tot;++i)
for(int j=0;j<26;++j)
if(son[i][j])
{
e[son[i][j]].push_back(i);
in[i]++;
}
int l=0,r=0;
for(int i=1;i<=tot;++i)
if(!in[i])
q[r++]=i;
while(l!=r)
{
int x=q[l++];
int now=0;
while(vis[x][now]) ++now;
ans[x]=now;
for(auto &y:e[x])
{
vis[y][ans[x]]=true;
--in[y];
if(!in[y])
q[r++]=y;
}
}
}

6.bzoj1396: 识别子串

给一个串,求每个位置的最短识别子串的长度,最短识别子串定义是,在整个串中出现一次且覆盖到这个位置的最短的一个子串。

做法是找endposendpos集合大小为 11 的那些串,用线段树维护答案,具体是区间和一个数取min,以及和一个等差数列取min,稍微转化一下就很好写了。


后缀自动机学习笔记
https://izard.space/2018/08/18/后缀自动机学习笔记/
作者
forever_you
发布于
2018年8月18日
许可协议