题目大意
考虑一个只包含小写拉丁字母的字符串 (s)。我们定义 (s) 的一个子串 (t) 的「出现值」为 (t) 在 (s) 中的出现次数乘以 (t) 的长度。请你求出 (s) 的所有回文子串中的最 大出现值。
(1 leqslant |s| leqslant 300,000)
题目链接
BZOJ 3676
题解
回文树模版。（人傻自带大常数系列。。。）
代码
调用 strlen() 时一定要记得 #include <cstring> 。。。（本机是给过的。。。）
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
|
#include <cstring>
#include <algorithm>
#include <new>
const int MAXN = 300005;
const int CHAR_SET = 'z' - 'a' + 1;
const char BASE_CHAR = 'a';
struct {
int str[MAXN];
int size;
struct Node {
int len, cnt;
Node *ch[CHAR_SET], *fail;
Node(int len = 0) : len(len), cnt(0) {
for (int i = 0; i < CHAR_SET; i++) ch[i] = NULL;
}
} *root[2], *last, nodes[MAXN], *curr;
PalinT() {
curr = nodes;
root[0] = last = new (curr++) Node(0);
root[1] = last->fail = new (curr++) Node(-1);
root[1]->fail = root[1];
str[size = 0] = -1;
}
Node *getFail(Node *u) {
while (str[size - u->len - 1] != str[size]) u = u->fail;
return u;
}
void insert(int c) {
str[++size] = c;
Node *o = getFail(last);
if (!o->ch[c]) {
Node *u = (o->ch[c] = new (curr++) Node(o->len + 2));
u->fail = o == root[1] ? root[0] : getFail(o->fail)->ch[c];
}
last = o->ch[c];
last->cnt++;
}
void build(char *s) {
int n = strlen(s);
for (int i = 0; i < n; i++) insert(s[i] - BASE_CHAR);
}
void count() {
Node *p = curr - 1;
for (; p != nodes; p--) p->fail->cnt += p->cnt;
p->fail->cnt += p->cnt;
}
} palinT;
int main() {
static char s[MAXN];
scanf("%s", s);
palinT.build(s);
palinT.count();
long long ans = 0;
for (PalinT::Node *p = palinT.nodes; p != palinT.curr; p++)
ans = std::max(ans, (long long) p->len * p->cnt);
printf("%lldn", ans);
return 0;
}
|
近期评论