注意事项：无。
后缀自动机
代码：
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
| int cntnd, root, last, son[MAXnd + 10][26 + 2], fail[MAXnd + 10], mxlen[MAXnd + 10];
int cntep[MAXnd + 10];
void init() {
cntnd = root = last = 1;
}
void extend(int ch) {
int a, b, c;
a = c = last;
b = last = ++cntnd;
mxlen[b] = mxlen[a] + 1;
cntep[b] = 1;
for (; c && son[c][ch] == 0; c = fail[c]) son[c][ch] = b;
if (c == 0) {
fail[b] = root;
} else {
int d = son[c][ch];
if (mxlen[d] == mxlen[c] + 1) {
fail[b] = d;
} else {
int e = ++cntnd;
memcpy(son[e], son[d], sizeof(son[e]));
fail[e] = fail[d];
mxlen[e] = mxlen[c] + 1;
fail[b] = fail[d] = e;
for (; c && son[c][ch] == d; c = fail[c]) son[c][ch] = e;
}
}
}
|
Luogu P3804 【模板】后缀自动机 (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
58
59
60
61
62
63
64
| const int MAXnd = MAXn * 2;
int head[MAXnd + 10], cntnex, nex[MAXnd + 10], to[MAXnd + 10];
void connect(int u, int v) {
nex[++cntnex] = head[u];
head[u] = cntnex;
to[cntnex] = v;
}
int cntnd, root, last, son[MAXnd + 10][26 + 2], fail[MAXnd + 10], mxlen[MAXnd + 10];
int cntep[MAXnd + 10];
void init() {
cntnd = root = last = 1;
}
void extend(int ch) {
int a, b, c;
a = c = last;
b = last = ++cntnd;
mxlen[b] = mxlen[a] + 1;
cntep[b] = 1;
for (; c && son[c][ch] == 0; c = fail[c]) son[c][ch] = b;
if (c == 0) {
fail[b] = root;
} else {
int d = son[c][ch];
if (mxlen[d] == mxlen[c] + 1) {
fail[b] = d;
} else {
int e = ++cntnd;
memcpy(son[e], son[d], sizeof(son[e]));
fail[e] = fail[d];
mxlen[e] = mxlen[c] + 1;
fail[b] = fail[d] = e;
for (; c && son[c][ch] == d; c = fail[c]) son[c][ch] = e;
}
}
}
void buildfailtree() {
for (int i = 1; i <= cntnd; ++i) {
if (i == root) continue;
connect(fail[i], i);
}
}
ll ans;
void dfs(int cur) {
for (int i = head[cur]; i; i = nex[i]) {
dfs(to[i]);
cntep[cur] += cntep[to[i]];
}
if (cntep[cur] > 1) ans = max(ans, (ll)cntep[cur] * mxlen[cur]);
}
int len; char str[MAXn + 10];
signed main() {
init();
scanf("%s", str + 1);
len = strlen(str + 1);
for (int i = 1; i <= len; ++i) {
extend(str[i] - 'a');
}
buildfailtree();
dfs(root);
printf("%lld\n", ans);
return 0;
}
|
伪广义后缀自动机
代码：
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
| int cntnd, root, last, son[MAXnd + 10][26 + 2], fail[MAXnd + 10], mxlen[MAXnd + 10];
void init() {
cntnd = root = last = 1;
}
void extend(int ch = -1) {
int a, b, c;
a = c = last;
b = last = ++cntnd;
mxlen[b] = mxlen[a] + 1;
if (ch == -1) {
fail[b] = root;
return;
}
for (; c && son[c][ch] == 0; c = fail[c]) son[c][ch] = b;
if (c == 0) {
fail[b] = root;
} else {
int d = son[c][ch];
if (mxlen[d] == mxlen[c] + 1) {
fail[b] = d;
} else {
int e = ++cntnd;
copy(begin(son[d]), end(son[d]), begin(son[e]));
fail[e] = fail[d];
mxlen[e] = mxlen[c] + 1;
fail[b] = fail[d] = e;
for (; c && son[c][ch] == d; c = fail[c]) son[c][ch] = e;
}
}
}
|
Luogu P6139 【模板】广义后缀自动机（广义 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
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXn = 4e5;
const int MAXlen = 1e6;
const int MAXsumlen = 1e6;
template <typename T>
inline void read(T &a) {
char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
read(a), read(argv...);
}
const int MAXnd = MAXn + MAXsumlen * 2;
int head[MAXnd + 10], cntnex, nex[MAXnd + 10], to[MAXnd + 10];
void connect(int u, int v) {
nex[++cntnex] = head[u];
head[u] = cntnex;
to[cntnex] = v;
}
int cntnd, root, last, son[MAXnd + 10][26 + 2], fail[MAXnd + 10], mxlen[MAXnd + 10];
void init() {
cntnd = root = last = 1;
}
void extend(int ch = -1) {
int a, b, c;
a = c = last;
b = last = ++cntnd;
mxlen[b] = mxlen[a] + 1;
if (ch == -1) {
fail[b] = root;
return;
}
for (; c && son[c][ch] == 0; c = fail[c]) son[c][ch] = b;
if (c == 0) {
fail[b] = root;
} else {
int d = son[c][ch];
if (mxlen[d] == mxlen[c] + 1) {
fail[b] = d;
} else {
int e = ++cntnd;
copy(begin(son[d]), end(son[d]), begin(son[e]));
fail[e] = fail[d];
mxlen[e] = mxlen[c] + 1;
fail[b] = fail[d] = e;
for (; c && son[c][ch] == d; c = fail[c]) son[c][ch] = e;
}
}
}
void buildfailtree() {
for (int i = 1; i <= cntnd; ++i) {
if (i == root) continue;
connect(fail[i], i);
}
}
int n;
int len[MAXn + 10]; char str[MAXlen + 10];
int suflen[MAXn + 10];
signed main() {
init();
read(n);
for (int i = 1; i <= n; ++i) {
scanf("%s", str + 1);
len[i] = strlen(str + 1);
for (int j = 1; j <= len[i]; ++j) {
extend(str[j] - 'a');
}
extend();
}
buildfailtree();
ll ans = 0;
for (int i = 1; i <= cntnd; ++i) {
if (i == root) continue;
ans += mxlen[i] - mxlen[fail[i]];
}
for (int i = n; i; --i) {
suflen[i] = suflen[i + 1] + (len[i] + 1);
}
for (int i = 1; i <= n; ++i) {
ans -= (ll)(len[i] + 1) * (suflen[i + 1] + 1);
}
printf("%lld\n", ans);
return 0;
}
|
