#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
char s[N]; // 1-indexed
int T, idx, Tree[N][26], link[N], len[N], occ[N] , num[N], n;
inline void extend(int p) {
while (s[p - len[T] - 1] != s[p]) T = link[T];
int x = link[T], c = s[p] - 'a';
while (s[p - len[x] - 1] != s[p]) x = link[x];
if (!Tree[T][c]) {
Tree[T][c] = ++idx;
len[idx] = len[T] + 2;
link[idx] = len[idx] == 1 ? 2 : Tree[x][c];
num[idx] = 1 + num[link[idx]];
} T = Tree[T][c],++occ[T];
}
long long build() {
long long tot_pal=0;
memset(Tree, 0, sizeof Tree);
memset(occ, 0, sizeof occ);
len[1] = -1, len[2] = 0;
link[1] = link[2] = 1;
T = idx = 2;
for (int i = 1; i <= n; i++) {
extend(i);
tot_pal+=num[T];
// cout<<"# "<<num[T]<<endl;
}
for (int i = idx; i > 2; i--) {
occ[link[i]] += occ[i];
}
// for(int i=3;i<=idx;i++)cout<<len[i]<<' '<<occ[i]<<endl;
return tot_pal;
}
int main(int argc, char const *argv[])
{
scanf("%s", s + 1);
n = strlen(s + 1);
build();
long long ma=0;
for(int i=3;i<=idx;i++)ma=max(ma,(long long)len[i]*(long long)occ[i]);
printf("%lld\n", ma);
return 0;
}
Compilation message
palindrome.cpp: In function 'int main(int, const char**)':
palindrome.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s + 1);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 2 |
Correct |
21 ms |
31992 KB |
Output is correct |
| 3 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 4 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 5 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 6 |
Correct |
19 ms |
32120 KB |
Output is correct |
| 7 |
Correct |
19 ms |
31996 KB |
Output is correct |
| 8 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 9 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 10 |
Correct |
20 ms |
31996 KB |
Output is correct |
| 11 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 12 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 13 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 14 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 15 |
Correct |
19 ms |
32120 KB |
Output is correct |
| 16 |
Correct |
20 ms |
31992 KB |
Output is correct |
| 17 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 18 |
Correct |
19 ms |
32120 KB |
Output is correct |
| 19 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 20 |
Correct |
20 ms |
31992 KB |
Output is correct |
| 21 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 22 |
Correct |
19 ms |
32120 KB |
Output is correct |
| 23 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 24 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 25 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 26 |
Correct |
20 ms |
31992 KB |
Output is correct |
| 27 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 28 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 29 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 30 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 31 |
Correct |
19 ms |
32120 KB |
Output is correct |
| 32 |
Correct |
20 ms |
31992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 2 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 3 |
Correct |
20 ms |
31980 KB |
Output is correct |
| 4 |
Correct |
19 ms |
31988 KB |
Output is correct |
| 5 |
Correct |
20 ms |
31992 KB |
Output is correct |
| 6 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 7 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 8 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 9 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 10 |
Correct |
20 ms |
31992 KB |
Output is correct |
| 11 |
Correct |
20 ms |
31992 KB |
Output is correct |
| 12 |
Correct |
19 ms |
31992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
32248 KB |
Output is correct |
| 2 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 3 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 4 |
Correct |
20 ms |
32124 KB |
Output is correct |
| 5 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 6 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 7 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 8 |
Correct |
19 ms |
31992 KB |
Output is correct |
| 9 |
Correct |
20 ms |
32120 KB |
Output is correct |
| 10 |
Correct |
20 ms |
32120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
33272 KB |
Output is correct |
| 2 |
Correct |
23 ms |
33376 KB |
Output is correct |
| 3 |
Correct |
22 ms |
33272 KB |
Output is correct |
| 4 |
Correct |
23 ms |
33272 KB |
Output is correct |
| 5 |
Correct |
23 ms |
33272 KB |
Output is correct |
| 6 |
Correct |
22 ms |
33016 KB |
Output is correct |
| 7 |
Correct |
22 ms |
33144 KB |
Output is correct |
| 8 |
Correct |
22 ms |
32248 KB |
Output is correct |
| 9 |
Correct |
22 ms |
32376 KB |
Output is correct |
| 10 |
Correct |
23 ms |
33144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
35832 KB |
Output is correct |
| 2 |
Correct |
30 ms |
35832 KB |
Output is correct |
| 3 |
Correct |
29 ms |
35832 KB |
Output is correct |
| 4 |
Correct |
28 ms |
35832 KB |
Output is correct |
| 5 |
Correct |
30 ms |
35832 KB |
Output is correct |
| 6 |
Correct |
28 ms |
35448 KB |
Output is correct |
| 7 |
Correct |
29 ms |
35192 KB |
Output is correct |
| 8 |
Correct |
28 ms |
32376 KB |
Output is correct |
| 9 |
Correct |
25 ms |
32376 KB |
Output is correct |
| 10 |
Correct |
28 ms |
35192 KB |
Output is correct |
| 11 |
Correct |
27 ms |
35832 KB |
Output is correct |
| 12 |
Correct |
26 ms |
32632 KB |
Output is correct |
