Bouvardia纠结了好久的后缀自动机……

Table of Contents

  1. Overview
  2. Definition
  3. Properties
  4. Construction
  5. Samples
    1. Luogu 3804
      1. Description
      2. Solution
      3. Code
    2. Luogu 1368
      1. Description
      2. Solution
    3. BZOJ 4032
      1. Description
      2. Solution

Overview

后缀自动机确实是个挺玄的东西呐. 是解决许多字符串问题强有力的工具.

顾名思义, 后缀自动机是能够识别一个字符串所有后缀的结构, 根据她的性质, 她同时可以识别一个字符串的所有字串.

Definition

定义超多的说…… Bouvardia也是翻来覆去研究了好久, 所以特意记在这里哦.

trans(St,c) : 在状态 St 后加入字符 c 到达的状态.

ST(str) : trans(init,str), 从初始状态读入字符串 str 后到达的状态.

Suf : 字符串 S 的后缀集合

Fac : 字符串 S 的连续字串集合

Right(α) : 字符串 α 在字符串 S 中出现位置右端点的集合.

Properties

可以发现, 如果得到了 Right(α), 又得到了一个 len , 我们就可以唯一确定一个字串.

那么我们不妨把所有 Right 集相等的子串压缩到一个状态下, 这时她的合法 len 就有了一个区间 [Min,Max], 当长度小于Min 时, Right 集可能会扩大, 这不符合定义, 相对地, 长度大于 Max 时, 由这个 Right 集和这个 len 确定的字串就不相等, 相应地 Right 集也不相等.

所以一个状态的可行长度一定是一个连续区间.

考虑两个状态 α,β, 有Right(α),Right(β), 记作Ra,Rb, 若Ra∩Rb=γ≠∅.

由于ST(α)≠ST(β)根据定义, stra,strb 没有交集. 由于 γ≠∅ , 所以[Min(α),Max(α)]∩[Min(β),Max(β)]=∅​.

不妨设 Max(α)<Min(β), 那么状态α表示的所有串都比β的短. 所以对于从 γ向前的所有可表出串, α 都是 β 的后缀, 又根据Right集合的定义, 会有所有α 中的元素跟随β作为后缀出现. 那么, 在每个 p∈Right(β) 向前的串, α 都是 β 的后缀, 即 Ra⊂Rb.

所以, 我们有:

{Ru⊂Rv,u suffix v Ru∩Rv=∅,otherwise.

由于Right 集合只有包含和不交关系, 这种关系实际构成了一颗树.

我们定义一颗Parent树, 则状态s在树上的直接父亲一定是满足Rs⊂Rfa中|R|最小的一个节点.

根据上面对Min的说明, 当长度为Min−1时, R集合一定进入了父亲的范围, 并且是首次进入, 所以我们有:

Max(fa)=Min(s)−1

定义状态NULL 为不存在 trans(init,str) 到达 ST(str). 反过来, 一个串str是S的字串当且仅当在 SAMS 中, ST(str)≠NULL.

而一个字串的出现次数就是她所在状态Right集合的大小.

实际应用中我们通常不直接求出每个状态的Right 集, 根据定义, 一定有:

Rights=⋃y∈son(s)Righty

所以利用DFS序的子树连续区间性质可以解决一些子串位置问题.

最后一个证明, 根据定义, 对于一个有限长度字符串S, SAMS 可以识别的串一定是有限个, 也即对于任意一个状态ST(str), 不存在一种trans(ST(str),str′), 使得trans(ST(str),str′)=ST(str),|str′|≠0, 否则|S|=∞, 与条件矛盾.

那么, 将 trans 视作边, 则SAM是一个DAG.

Construction

对于当前字符串 T, 新加入字符 c, 我们要

SAMT →SAMTc

添加字符后, 我们得到了一些新的子串, 她们一定是Tc的后缀, 而这些后缀一定是在 T的后缀后面添加一个 c.

定义T的右端点 Q, 考虑所有能表示T的后缀的节点 v1,v2,v3,…, 由于一定存在一个节点P, 使得Right(P)={L}, 所以v1,v2,v3,… 在 Parent 树上一定是 P 的祖先.

插入字符后, 新建一个节点nP=ST(Tc), 则Right(nP)={Q+1}. 不妨按照从后代到祖先的顺序定义: v1=P,v2,…,vk=root.

对于每个v, 若Right(v)中除不考虑 rn=Q 外没有符合要求的元素, 则连一条边 vc→nP, 这是这个状态首次可以转移到结尾为c的状态.

再考虑 vp为 1…k 中第一个有标号为 c 的边的状态. 不考虑rn, 令q=trans(vp,c), 那么Right(q)={ri+1|Tri+1=c} , 但是我们不能直接在 Right(q) 中添加一个元素 Q+1.

例如对于一个 vp, 长度为 Max(vp)的串:

AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

而对于q, 长度为Max(q)的串:

AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

如果在她的 Right 集中插入 Q+1, 则修改了Max(q), 这是错误的.

当然, 如果恰好有 Max(q)=Max(vp)+1, 即我们可以直接在一个字串后连接一个字符c来转移到q状态, 那么在整个T后连接一个当然也是合法转移. 所以直接令Parent(nP)=q 即可.

继续考虑当前状态. 我们可以新建一个节点 nQ, 使得Right(nQ)=Right(q)∪{Q+1}, 这个新节点是可以通过vp直接连接一个c得到的, 所以Max(nQ)=Max(vp)+1.

那么一定有 Right(q)⊂Right(nQ), 故新的 Parent(q)=nQ, 同时因为 nQ 是我们目前有的第一个包含了Q+1 和其他元素的节点, 故Parent(nP)=nQ. 又因为 Right(q)⊂Right(Parent(q)former), 新的nQ节点能表示的串一定是q能表示的串的一个后缀, 不会越过范围表示其他的串, 所以她可以继承q的真子集特性, 那么Parent(nQ)=Parent(q)former. 同时后缀这个性质还可以帮助我们得出, trans(nQ)=trans(q).

最后, 我们处理原来转移到 q 的一段v节点, 在添加新字符后, 她们实际可以转移到的状态较 q 扩充了, 所以将 q 替换为 nQ 即可.

至此, SAM的扩展操作就全部完成啦, 按顺序扩展就可以建出整个字符串的SAM！

结合代码食用喵~

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
struct SuffixAutomation
{
	int tr[maxn][26], fa[maxn], mx[maxn];
	int lst, cnt;
	void Insert(int c)
	{
		int p = lst, np = ++cnt;
		lst = np; mx[np] = mx[p] + 1;
		for(;p && !tr[p][c]; p = fa[p]) tr[p][c] = np;
		if(!p) fa[np] = 1;
		else
		{
			int q = tr[p][c];
			if(mx[p] + 1 == mx[q]) fa[np] = q;
			else
			{
				int nq = ++cnt;mx[nq] = mx[p] + 1;
				memcpy(t[nq].tr, t[q].tr, sizeof(t[q].tr));
				fa[nq] = fa[q]; fa[q] = fa[np] = nq;
				for(; tr[p][c] == q; p = fa[p]) tr[p][c] = nq;
			}
		}
		siz[np] = 1;
	}
}

Samples

Luogu 3804

Description

给定一个字符串，求其出现次数 × 长度的最大值。

Solution

根据Parent树的特性，按Right集大小做基数排序，倒序累加，一定可以保证儿子的贡献累加到父亲上。而在相同次数下，能产生贡献的一定是最长串，所以用sizx×Max(x) 更新答案就好啦。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//in struct SuffixAutoMation:	
	void build()
    {
        scanf("%s", str + 1); n = strlen(str + 1);
        lst = cnt = 1;
        for(int i = 1; i <= n; ++i)
            Insert(str[i] - 'a');
    }
    void solve()
    {
        for(int i = 1; i <= cnt; ++i) bkt[mx[i]]++;
        for(int i = 1; i <= cnt; ++i) bkt[i] += bkt[i - 1];
        for(int i = 1; i <= cnt; ++i) arr[bkt[mx[i]]--] = i;
        for(int i = cnt; i; --i)
        {
            int cur = arr[i];
            siz[fa[cur]] += siz[cur];
            if(siz[cur] > 1) ans = max(ans, (ll)siz[cur] * (ll)mx[cur]);
        }
        printf("%lld\n", ans);
    }

Luogu 1368

Description

求一个字符串循环同构串中字典序最小的串.

Solution

把字符串在SAM上插入两遍, 从根节点开始每次选最小的转移边转移, 直到转移n次.

字符集比较大, 用map.

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
struct SuffixAutoMation
{
    map<int, int> tr[maxn];
    int fa[maxn], mx[maxn];
    int lst, cnt;
    void Insert(int c)
    {
        int p = lst, np = ++cnt;
        lst = np; mx[np] = mx[p] + 1;
        for(; p && !tr[p].count(c); p = fa[p]) tr[p][c] = np;
        if(!p) fa[np] = 1;
        else
        {
            int q = tr[p][c];
            if(mx[p] + 1 == mx[q]) fa[np] = q;
            else
            {
                int nq = ++cnt; mx[nq] = mx[p] + 1;
                tr[nq] = tr[q];
                fa[nq] = fa[q]; fa[q] = fa[np] = nq;
                for(; tr[p][c] == q; p = fa[p]) tr[p][c] = nq; 
            }
        }
    }
    void build()
    {
        scanf("%d", &n);
        lst = cnt = 1;
        for(int i = 1; i <= n; ++i)
            str[i] = rd();
        for(int i = 1; i <= n; ++i) Insert(str[i]);
        for(int i = 1; i <= n; ++i) Insert(str[i]);
    }
    void solve()
    {
        int now = 1;
        for(int i = 1; i <= n; ++i)
        {
            printf("%d ", tr[now].begin()->first);
            now = tr[now].begin()->second;
        }
    }
}SAM;

BZOJ 4032

Description

在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。

一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。

一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。

下面，给两个小写字母串A，B，请你计算：

(1) A的一个最短的子串，它不是B的子串

(2) A的一个最短的子串，它不是B的子序列

(3) A的一个最短的子序列，它不是B的子串

(4) A的一个最短的子序列，它不是B的子序列

Solution

我们可以O(n2)地建出一个序列自动机.

好吧其实这就是暴力的说.

也就是贪心地匹配子序列的转移.

对于每个问题在相应的自动机上跑BFS就好啦.

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <bitset>

using namespace std;

const int maxn = 2005;

char a[maxn], b[maxn];

struct SuffixAutomation
{
	int tr[maxn << 1][26], mx[maxn << 1], fa[maxn << 1];
	int lst, cnt;
	SuffixAutomation()
	{
		lst = cnt = 1;
	}
	void Insert(int c)
	{
		int p = lst, np = ++cnt;
		lst = np; mx[np] = mx[p] + 1;
		for(; p && !tr[p][c]; p = fa[p]) tr[p][c] = np;
		if(!p) fa[np] = 1;
		else
		{
			int q = tr[p][c];
			if(mx[p] + 1 == mx[q]) fa[np] = q;
			else
			{
				int nq = ++cnt; mx[nq] = mx[p] + 1;
				memcpy(tr[nq], tr[q], sizeof(tr[q]));
				fa[nq] = fa[q]; fa[q] = fa[np] = nq;
				for(; tr[p][c] == q; p = fa[p]) tr[p][c] = nq;
			}
		}
	}
}sama, samb;
struct SeqAutomation
{
	int tr[maxn][26], lst[26], pre[maxn];
	int cnt;
	SeqAutomation()
	{
		cnt = 1;
		for(int i = 0; i < 26; ++i) lst[i] = 1;
	}
	void Insert(int c)
	{
		int np = ++cnt;
		pre[np] = lst[c];
		for(int i = 0; i < 26; ++i)
		{
			for(int j = lst[i]; j && !tr[j][c]; j = pre[j])
				tr[j][c] = np;
		}
		lst[c] = np;
	}
}seqa, seqb;
struct node
{
	int a, b, len;
	node(int a_ = 0, int b_ = 0, int l = 0):
		a(a_), b(b_), len(l){};
};
bitset<maxn << 1> vis[maxn << 1];

inline void sam_sam()
{
	queue<node> q;
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = sama.tr[u.a][i], yb = samb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}
inline void sam_seq()
{
	queue<node> q;
	for(int i = 0; i < (maxn << 1); ++i) vis[i].reset();
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = sama.tr[u.a][i], yb = seqb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}
inline void seq_sam()
{
	for(int i = 0; i < (maxn << 1); ++i) vis[i].reset();
	queue<node> q;
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = seqa.tr[u.a][i], yb = samb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			else if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}
inline void seq_seq()
{
	for(int i = 0; i < (maxn << 1); ++i) 
		vis[i].reset();
	queue<node> q;
	q.push(node(1, 1, 0));
	vis[1][1] = 1;
	while(!q.empty())
	{
		node u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int ya = seqa.tr[u.a][i], yb = seqb.tr[u.b][i];
			if(ya && yb)
			{
				if(vis[ya][yb]) continue;
				q.push(node(ya, yb, u.len + 1));
				vis[ya][yb] = 1;
			}
			else if(ya && !yb) {printf("%d\n", u.len + 1); return;}
		}
	}
	puts("-1");
	return;
}

int main()
{
	scanf("%s", a);
	scanf("%s", b);
	int la = strlen(a), lb = strlen(b);
	for(int i = 0; i < la; ++i) sama.Insert(a[i] - 'a');
	for(int i = 0; i < lb; ++i) samb.Insert(b[i] - 'a');
	for(int i = 0; i < la; ++i) seqa.Insert(a[i] - 'a');
	for(int i = 0; i < lb; ++i) seqb.Insert(b[i] - 'a');
	sam_sam();
	sam_seq();
	seq_sam();
	seq_seq();
	return 0;
}