#include <bits/stdc++.h>
using namespace std;
char str[300005];
int n;
int len[300005], ch[300005][26], q[300005][26];
int r[300005], f[300005];
char s[101];
int h, t, cnt;
long long sum = 0;
int st, ed;
vector<int> E[300005];
void init() {
for (int i = 0; i < 2; i ++) memset(ch[i], 0, sizeof(ch[i]));
len[0] = 0; len[1] = -1;
for (int i = 0; i < 26; i ++) q[0][i] = 1;
f[0] = 1; f[1] = 1;
st = ed = 0;
cnt = 1;
sum = 0;
}
bool valid(int x) {
return 1 <= x && x <= t;
}
void front_ins(int x) {
if (str[x + len[st] + 1] != str[x]) st = q[st][str[x] - 'a'];
if (!ch[st][str[x] - 'a']) {
int j = f[st];
if (str[x + len[j] + 1] != str[x]) j = q[j][str[x] - 'a'];
//while (str[x + len[j] + 1] != str[x]) j = f[j];
len[++ cnt] = len[st] + 2;
int ff = ch[j][str[x] - 'a'];
f[cnt] = ff;
for (int k = 0; k < 26; k ++) q[cnt][k] = q[ff][k];
char chx = str[x + len[ff]];
q[cnt][chx - 'a'] = ff;
E[ff].push_back(cnt);
ch[st][str[x] - 'a'] = cnt;
memset(ch[cnt], 0, sizeof(ch[cnt]));
}
st = ch[st][str[x] - 'a'];
r[st] ++;
// sum += r[st];
if (len[st] == t - h) ed = st;
}
void back_ins(int x) {
//while (!valid(x - len[ed] - 1) || str[x - len[ed] - 1] != str[x]) ed = f[ed];
if (str[x - 1 - len[ed]] != str[x]) ed = q[ed][str[x] - 'a'];
if (!ch[ed][str[x] - 'a']) {
int j = f[ed];
if (str[x - 1 - len[j]] != str[x]) j = q[j][str[x] - 'a'];
// while (!valid(x - len[j] - 1) || str[x - len[j] - 1] != str[x]) j = f[j];
len[++ cnt] = len[ed] + 2;
int ff = ch[j][str[x] - 'a'];
f[cnt] = ff;
for (int k = 0; k < 26; k ++) q[cnt][k] = q[ff][k];
char chx = str[x - len[ff]];
q[cnt][chx - 'a'] = ff;
E[ff].push_back(cnt);
ch[ed][str[x] - 'a'] = cnt;
memset(ch[cnt], 0, sizeof(ch[cnt]));
}
ed = ch[ed][str[x] - 'a'];
r[ed] ++;
// sum += r[ed];
if (len[ed] == t - h) st = ed;
}
void dfs(int x) {
for (int i = 0; i < (int )E[x].size(); i ++) {
dfs(E[x][i]);
r[x] += r[E[x][i]];
}
}
int main( ) {
init();
scanf("%s", str + 1);
n = (int )strlen(str + 1);
for (int i = 1; i <= n; i ++) {
++ t;
back_ins(i);
}
dfs(0);
for (int i = 2; i <= cnt; i ++) {
sum = max(sum, 1LL * r[i] * len[i]);
}
printf("%lld\n", sum);
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str + 1);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
8 ms |
7296 KB |
Output is correct |
3 |
Correct |
8 ms |
7424 KB |
Output is correct |
4 |
Correct |
8 ms |
7552 KB |
Output is correct |
5 |
Correct |
8 ms |
7424 KB |
Output is correct |
6 |
Correct |
8 ms |
7424 KB |
Output is correct |
7 |
Correct |
8 ms |
7424 KB |
Output is correct |
8 |
Correct |
8 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
8 ms |
7424 KB |
Output is correct |
11 |
Correct |
8 ms |
7424 KB |
Output is correct |
12 |
Correct |
8 ms |
7424 KB |
Output is correct |
13 |
Correct |
8 ms |
7424 KB |
Output is correct |
14 |
Correct |
9 ms |
7424 KB |
Output is correct |
15 |
Correct |
9 ms |
7424 KB |
Output is correct |
16 |
Correct |
9 ms |
7424 KB |
Output is correct |
17 |
Correct |
8 ms |
7424 KB |
Output is correct |
18 |
Correct |
8 ms |
7424 KB |
Output is correct |
19 |
Correct |
8 ms |
7424 KB |
Output is correct |
20 |
Correct |
8 ms |
7424 KB |
Output is correct |
21 |
Correct |
8 ms |
7424 KB |
Output is correct |
22 |
Correct |
8 ms |
7424 KB |
Output is correct |
23 |
Correct |
8 ms |
7424 KB |
Output is correct |
24 |
Correct |
8 ms |
7424 KB |
Output is correct |
25 |
Correct |
8 ms |
7424 KB |
Output is correct |
26 |
Correct |
8 ms |
7424 KB |
Output is correct |
27 |
Correct |
8 ms |
7424 KB |
Output is correct |
28 |
Correct |
8 ms |
7424 KB |
Output is correct |
29 |
Correct |
8 ms |
7424 KB |
Output is correct |
30 |
Correct |
8 ms |
7424 KB |
Output is correct |
31 |
Correct |
8 ms |
7424 KB |
Output is correct |
32 |
Correct |
8 ms |
7424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7680 KB |
Output is correct |
2 |
Correct |
8 ms |
7680 KB |
Output is correct |
3 |
Correct |
9 ms |
7680 KB |
Output is correct |
4 |
Correct |
9 ms |
7680 KB |
Output is correct |
5 |
Correct |
8 ms |
7680 KB |
Output is correct |
6 |
Correct |
10 ms |
7680 KB |
Output is correct |
7 |
Correct |
8 ms |
7680 KB |
Output is correct |
8 |
Correct |
8 ms |
7680 KB |
Output is correct |
9 |
Correct |
8 ms |
7552 KB |
Output is correct |
10 |
Correct |
8 ms |
7424 KB |
Output is correct |
11 |
Correct |
8 ms |
7424 KB |
Output is correct |
12 |
Correct |
8 ms |
7552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10112 KB |
Output is correct |
2 |
Correct |
11 ms |
9984 KB |
Output is correct |
3 |
Correct |
11 ms |
10368 KB |
Output is correct |
4 |
Correct |
10 ms |
10264 KB |
Output is correct |
5 |
Correct |
12 ms |
9728 KB |
Output is correct |
6 |
Correct |
10 ms |
9728 KB |
Output is correct |
7 |
Correct |
11 ms |
9984 KB |
Output is correct |
8 |
Correct |
8 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
10 ms |
8960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
34424 KB |
Output is correct |
2 |
Correct |
29 ms |
33400 KB |
Output is correct |
3 |
Correct |
31 ms |
36864 KB |
Output is correct |
4 |
Correct |
31 ms |
35096 KB |
Output is correct |
5 |
Correct |
30 ms |
30208 KB |
Output is correct |
6 |
Correct |
24 ms |
25088 KB |
Output is correct |
7 |
Correct |
28 ms |
28792 KB |
Output is correct |
8 |
Correct |
10 ms |
7680 KB |
Output is correct |
9 |
Correct |
17 ms |
14336 KB |
Output is correct |
10 |
Correct |
26 ms |
26752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
88696 KB |
Output is correct |
2 |
Correct |
70 ms |
83576 KB |
Output is correct |
3 |
Correct |
77 ms |
95736 KB |
Output is correct |
4 |
Correct |
71 ms |
86776 KB |
Output is correct |
5 |
Correct |
104 ms |
76664 KB |
Output is correct |
6 |
Correct |
65 ms |
75128 KB |
Output is correct |
7 |
Correct |
62 ms |
69880 KB |
Output is correct |
8 |
Correct |
14 ms |
8064 KB |
Output is correct |
9 |
Correct |
14 ms |
8064 KB |
Output is correct |
10 |
Correct |
67 ms |
64120 KB |
Output is correct |
11 |
Correct |
77 ms |
84088 KB |
Output is correct |
12 |
Correct |
22 ms |
16000 KB |
Output is correct |