Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

后缀自动机

Posted on

后缀数组都没懂得蒻犇就被巨佬们卷来听后缀自动机，太难了QWQ

简介

SAM的性质

  • $SAM$ 是一个状态机。一个起点，若干终点。原串的所有的字串和从 $SAM$ 起点开始的所有路径一一对应，不重不漏。所以终点就是包含所有后缀的点。
  • 每个点包含若干字串，每个子串都一一对应一条从起点到该点的路径。且这些字串一定是里面最长字串的连续后缀。

SAM问题中经常考虑的两种边

  • 普通边，类似于 $Trie$。表示在某个状态所表示的所有字串的后面添加一个字串。
  • $Link$、$Father$。表示将某个状态所表示的最短字串的首字母删除。这类边构成一棵树。

SAM的构造思路

  • $endpos(s)$：子串s所有出现的位置（尾字母下标）集合。$SAM$ 中的每个状态都一一对应一个 $endpos$ 的等价类。

endpos的性质：

  • 令 $s1,s2$ 为 S 的两个子串 ，不妨设 $|s1|≤|s2|$ （我们用 $|s|$ 表示 $s$ 的长度 ，此处等价于 $s_1$ 不长于 $s_2$ ）。则 $s_1$ 是 $s_2$ 的后缀当且仅当 $endpos(s_1)⊇endpos(s_2)$ ，$s_1$ 不是 $s_2$ 的后缀当且仅当 $endpos(s_1)∩endpos(s_2)=∅$　。
  • 两个不同子串的 $endpos$，要么有包含关系，要么没有交集。
  • 两个子串的 $endpos$ 相同，那么短串为长串的后缀。
  • 对于一个状态 $st$ ，以及任意的 $longest(st)$ 的后缀 $s$ ，如果 $s$ 的长度满足：$|shortest(st)|≤|s|≤|longsest(st)|$ ，那么 $s∈substrings(st)$ 。

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
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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e6 + 5;
int n;
int tot = 1, last = 1;
struct Node{
	int len, fa;
	int ch[26];
}node[N];
char str[N];
LL f[N];
LL ans;
int idx;
int e[N], ne[N], h[N];
void extend(int c)
{
	int p = last, np = last = ++ tot; // 插入新状态
	f[tot] = 1;
	node[np].len = node[p].len + 1;
	for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
	if(!p) node[np].fa = 1;
	else{
		int q = node[p].ch[c];
		if(node[q].len == node[p].len + 1) node[np].fa = q;
		else{
			int nq = ++ tot;
			node[nq] = node[q], node[nq].len = node[p].len + 1;
			node[q].fa = node[np].fa = nq;
			for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
		}
	}
}
void add(int x, int y)
{
	idx ++;
	e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
void dfs(int x)
{
	for(int i = h[x]; ~i; i = ne[i])
	{
		dfs(e[i]);
		f[x] += f[e[i]];
	}
	if(f[x] > 1) ans = max(ans, f[x] * node[x].len);
}
int main()
{
	scanf("%s", str);
	for(int i = 0; str[i];i ++) extend(str[i] - 'a');
	memset(h, -1, sizeof(h));
	for(int i = 2; i <= tot; i ++) add(node[i].fa, i);
	dfs(1);
	printf("%lld\n", ans);
	return 0;
}