P3804-【模板】后缀自动机 (SAM)
题目:
题目描述:
给定一个只包含小写字母的字符串$S$,
请你求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。
输入格式:
一行一个仅包含小写字母的字符串$S$
输出格式:
一个整数，为 所求答案
样例:
样例输入 1:
样例输出 1:
思路:
实现:
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
| #include "ybwhead/ios.h"
long long ans;
int n, nl;
const int maxn = 3 * 1e6 + 100;
char s[maxn];
struct sam
{
int mp[maxn][26];
struct edge
{
int nxt, v;
} e[maxn];
int tot, cnt, las, len[maxn], head[maxn], siz[maxn], fa[maxn];
void add(int u, int v)
{
e[++tot].v = v;
e[tot].nxt = head[u];
head[u] = tot;
}
void ins(int c)
{
int p = las;
siz[las = ++cnt] = 1;
len[las] = nl;
for (; p && mp[p][c] == 0; p = fa[p])
{
mp[p][c] = las;
}
if (p == 0)
{
fa[las] = 1;
return;
}
int q = mp[p][c];
if (len[p] + 1 == len[q])
{
fa[las] = q;
return;
}
len[++cnt] = len[p] + 1;
for (int i = 0; i < 26; i++)
{
mp[cnt][i] = mp[q][i];
}
fa[cnt] = fa[q];
fa[q] = cnt;
fa[las] = cnt;
for (int i = p; mp[i][c] == q; i = fa[i])
{
mp[i][c] = cnt;
}
}
inline void jt()
{
for (int i = 2; i <= cnt; i++)
{
add(fa[i], i);
}
}
void dfs(int u)
{
for (int i = head[u]; i; i = e[i].nxt)
{
dfs(e[i].v);
siz[u] += siz[e[i].v];
}
if (siz[u] != 1)
{
ans = max(ans, (long long)siz[u] * len[u]);
}
}
} sam;
int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
sam.cnt = sam.las = 1;
for (nl = 1; nl <= n; nl++)
sam.ins(s[nl] - 'a');
sam.jt();
sam.dfs(1);
yout << ans << endl;
return 0;
}
|