Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

学习笔记 SAM

Posted on Edited on In

垂死病中惊坐起, 笑闻学弟切SAM

是时候补一篇学习笔记了

为啥每次我打后缀自动机都出来孩子战斗机啊

定义

// 基本上是自己瞎捷豹编的

s: SAM的起点, 一切转移从这里开始...

endpos[(string) x]: 字符串x在原串中出现位置(取x结尾的下标)的集合

终点: 所有endpos包含n的节点都是终点(感谢yt姐姐告诉我终点有很多个qwq)

节点: 自动机中的点, 一个节点包含着一类endpos相同(必须 完 全 一 致 )的子串

maxlen[x]和minlen[x]: 代表节点x中包含的长度最长的子串和长度最短的子串(有的时候也省略为起长度)

节点后缀: 对于节点x, 节点后缀就是maxlen[x]的所有后缀, 显然这个节点包含的所有的子串属于这个点的节点后缀, 而长度大于minlen[x]的节点后缀就是这个节点所包含的节点

边: - trans[x][y]: 在节点x处后一个字符为y时转移到的节点; 如果不能识别, trans[x][y] = NULL - suff_link[x]: 指向 [包含 [第一个长度小于minlen[x]的节点后缀] 的节点], 因为minlen沿着suff_link是单调递减的, 所以最后一定会变为空串, 即指向初始节点s - suff_path[x]: 从节点x开始, 由suff_link一直向上, 组成的路径, 终点为s(显然suff_path[x]上的节点的endpos都会包含endpos[x])

转移

// 一个大分类讨论...

maxlen为当前串的节点为x, 新加入的字符为y...我们现在需要给所有合法的后缀都在后面加上一个字符y, 因为原串扩充了一位所以肯定要增加一个节点, 先++cntn为敬

I

对于任意节点\(j \in \text{suff_path[x]}\), 都有trans[j][y] = NULL

也就是所有的终点(suff_path[x]上所有点的endpos都包含n, 也就是说他们都是终点)即当前串的所有后缀在当前串的子串都不能向y转移, 既然坑上没有萝卜我们就可以直接让suff_path上的节点trans[j][y] = cntn; 最后让suff_link[cntn] = s, 因为之前的串上没有trans[j][y], 终点又变成1个了

II

在沿着suff_path[x]向上跳的时候, 对于trans[j][y] = NULL的点, 同I我们可以直接把他们的trans赋成cntn;

而遇到trans[j][y] != NULL且maxlen[trans[j][y]] = maxlen[j] + 1(为什么放在下面说)的情况时, 我们发现我们没有必要继续向上跳了(上面的点也一定有trans[j][y] != NULL)我们可以直接把这些trans[j][y]作为终点, 让suff_link[x] = trans[j][y]然后就可以直接返回了

III

在沿着suff_path[x]向上跳的时候, trans[j][y] = NULL时处理还是同上

否则trans[j][y] != NULL且maxlen[trans[j][y]] > maxlen[j] + 1: 这个trans[j][y]并不是直接由j转移来的, 所以如果我们把这个点当做一个终点的话, 就会造成非后缀被识别为后缀(因为到达了终点), 所以我们要复制一个新点;

我们新建一个点c, suff_link[c] = suff_link[trans[j][y]], trans[c] = trans[trans[j][y]], maxlen[c] = maxlen[j] + 1, 即我们新建一个节点作为终点, 且是只由j转移来的, 然后后面的就和II是一样的了: suff_link[cntn] = c

然后再做一些处理: 修改suff_link[trans[j][y]] = c(节点c与trans[j][y]的最长公共后缀是最长的); 沿着suff_path[j]向上走, 对于路径上所有通过y转移到trans[j][y]的节点g: trans[g][y] = c(这些节点的后缀都是j的后缀, 加上y后也就是新串的后缀);

是不是也不是很难?

几道例题

后缀自动机二·重复旋律5

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXZ = 26, MAXN = 1000000 + 5;
struct SAM {
	struct node {
		int trans[MAXZ], suff_link, maxlen;
		node (int ml = 0): suff_link(0), maxlen(ml) { memset(trans, 0, sizeof(trans)); }
	} b[MAXN * 2];
	int s, last, cntb;
	void init() { s = last = cntb = 1; }
	int ins(char xc) {
		int y = xc - 'a', dq = ++cntb, dql = last;
		b[dq] = node(b[dql].maxlen + 1);
		for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link)	b[dql].trans[y] = dq;
		if (!dql)	b[dq].suff_link = s;
		else if (b[b[dql].trans[y]].maxlen == b[dql].maxlen + 1)	b[dq].suff_link = b[dql].trans[y];
		else {
			int c = ++cntb, bd = b[dql].trans[y];
			b[c] = node(b[dql].maxlen + 1);
			for (int i = 0; i < MAXZ; i++)	b[c].trans[i] = b[bd].trans[i];
			b[c].suff_link = b[bd].suff_link;
			b[bd].suff_link = b[dq].suff_link = c;
			for (; dql && b[dql].trans[y] == bd; dql = b[dql].suff_link)	b[dql].trans[y] = c;
		}
		return (last = dq);
	}
}refun;
int main() {
	refun.init();
	char srs[MAXN];
	scanf("%s", srs);
	int n = strlen(srs);
	LL ans = 0;
	for (int i = 0; i < n; i++) {
		int last = refun.ins(srs[i]);
		ans += (refun.b[last].maxlen - refun.b[refun.b[last].suff_link].maxlen);
	}
	printf("%lld", ans);
	return 0;
}

后缀自动机三·重复旋律6

这题还是挺有意思的

endpos[x]就是所有suff_link[j] == x(这些j被称为\(parent\)树上x的儿子)的endpos的并(看不懂的去瞅一眼定义...); 如果这个x包含了总串的某个前缀, 这个endpos[x]还要再加上自身的位置(这个位置肯定不会包含在x的儿子中, 因为儿子都比x要长, 不会是原串这个位置的前缀)

然后数组开小了加上手残调了一个多小时...

我不知道我都干了什么...

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXZ = 26, MAXN = 1000000 + 5;
struct SAM {
	struct node {
		int  maxlen, suff_link, trans[MAXZ];
		node(int maxlen = 0): maxlen(maxlen), suff_link(0) { memset(trans, 0, sizeof(trans)); }
	} b[MAXN << 1];
	int s, last, cntb;
	void init() { s = last = cntb = 1; }
	int ins(char xc) {
		int dq = ++cntb, y = xc - 'a', dql = last;
		b[dq] = node(b[last].maxlen + 1);
		for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link)	b[dql].trans[y] = dq;
		if (!dql)	b[dq].suff_link = s;
		else if (b[dql].maxlen + 1 == b[b[dql].trans[y]].maxlen)	b[dq].suff_link = b[dql].trans[y];
		else {
			int c = ++cntb, dqd = b[dql].trans[y];
			b[c] = node(b[dql].maxlen + 1); // 这个地方一不小心打成 b[c] = node(b[last].maxlen + 1); 了...我也不知道我怎么搞的...
			b[c].suff_link = b[dqd].suff_link;
			b[dqd].suff_link = b[dq].suff_link = c;
			for (int i = 0; i < MAXZ; i++)	b[c].trans[i] = b[dqd].trans[i];
			for (; dql && b[dql].trans[y] == dqd; dql = b[dql].suff_link)	b[dql].trans[y] = c;
		}
		return (last = dq);
	}
}refun;
struct edg {
	int to, next;
} b[MAXN << 1];
int g[MAXN << 1], cntb, size[MAXN << 1], ans[MAXN]; 
void adn(int from, int to) {
	b[++cntb].next = g[from];
	b[cntb].to = to;
	g[from] = cntb;
}
int dfs(int dq) {
	for (int i = g[dq]; i; i = b[i].next)	size[dq] += dfs(b[i].to);
	ans[refun.b[dq].maxlen] = max(ans[refun.b[dq].maxlen], size[dq]);
	return size[dq];
}
int main() {
	refun.init();
	int n = 0;
	do {
	    char src = getchar();
	    if (src < 'a' || src > 'z') break;
		size[refun.ins(src)] = 1, ++n;
	} while (true);
	for (int i = 2; i <= refun.cntb; i++)	adn(refun.b[i].suff_link, i);
	dfs(1);
	for (int i = n - 1; i >= 1; i--)	ans[i] = max(ans[i], ans[i + 1]);
	for (int i = 1; i <= n; i++)	printf("%d\n", ans[i]);
	return 0;
}

后缀自动机四·重复旋律7

这种有多个串的题...如果一个答案只能在一个位置算贡献, 我们就不能对多个串分开来算了, 我们可以把这些串都拼在一起, 然后在中间加上不可见字符作为分割

这样这个题就很简单了...

忘初始化了...身败名裂

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (2000000 + 5)
#define MAXZ (11)
#define Refun (1000000000 + 7)
#define LL long long
using namespace std;
struct SAM {
	struct node {
		int maxlen, suff_link, trans[MAXZ], vsize; 
		LL sum;
		node(int maxlen = 0): maxlen(maxlen), suff_link(0), sum(0), vsize(0) { memset(trans, 0, sizeof(trans)); }
	} b[MAXN << 1];
	int s, last, cntb, du[MAXN];
	bool inq[MAXN << 1];
	void init() { s = last = cntb = 1; }
	void ins(int y) {
		int dq = ++cntb, dql = last;
		b[dq] = node(b[dql].maxlen + 1);
		for (; dql && !b[dql].trans[y]; dql = b[dql].suff_link) b[dql].trans[y] = dq;
		if (!dql) b[dq].suff_link = s;
		else if (b[dql].maxlen + 1 == b[b[dql].trans[y]].maxlen) b[dq].suff_link =b[dql].trans[y];
		else {
			int c = ++cntb, dqd = b[dql].trans[y];
			b[c] = node(b[dql].maxlen + 1);
			b[c].suff_link = b[dqd].suff_link;
			for (int i = 0; i < MAXZ; i++) b[c].trans[i] = b[dqd].trans[i];
			b[dqd].suff_link = b[dq].suff_link = c;
			for (; dql && b[dql].trans[y] == dqd; dql = b[dql].suff_link) b[dql].trans[y] = c;
		}
		last = dq;
	}
	void solve() {
		LL ans = 0;
		for (int i = 1; i <= cntb; i++)
			for (int j = 0; j < MAXZ; j++)
				if (b[i].trans[j])
					++du[b[i].trans[j]];
		queue<int> q;
		q.push(1);
		b[1].vsize = 1;
		while (!q.empty()) {
			int dq = q.front();
			ans = (ans + b[dq].sum) % Refun;
			q.pop();
			for (int i = 0; i < MAXZ; i++)
				if (b[dq].trans[i]) {
					--du[b[dq].trans[i]];
					if (i != 10) {
						b[b[dq].trans[i]].vsize += b[dq].vsize;
						b[b[dq].trans[i]].sum = (b[b[dq].trans[i]].sum + b[dq].sum * 10 + i * b[dq].vsize) % Refun;
					}
					if (!du[b[dq].trans[i]])
						q.push(b[dq].trans[i]);
				}
		}
 		printf("%lld", ans);
	}
} refun;
int n;
char s[MAXN];
int main() {
	scanf("%d", &n);
	refun.init();
	for (int i = 1; i <= n; i++) {
		scanf("%s", s);
		int tn = strlen(s);
		for (int j = 0; j < tn; j++)
			refun.ins(s[j] - '0');
		refun.ins(10);
	}
	refun.solve();
	return 0;
}

后缀自动机五·重复旋律8

1
咕咕咕

By 准备退役旅游的 Cansult