#include <bits/stdc++.h>
using namespace std;
#define int long long
struct PalTree {
struct Node {
map<char, int> leg;
int link, len, cnt;
};
vector<Node> T;
int nodes = 2;
int ans = 0;
PalTree(string str) : T(str.size() + 2) {
T[1].link = T[1].len = 0;
T[0].link = T[0].len = -1;
int last = 0;
for (int i = 0; i < (int)str.size(); ++i) {
char now = str[i];
int node = last;
while (now != str[i - T[node].len - 1])
node = T[node].link;
if (T[node].leg.count(now)) {
node = T[node].leg[now];
T[node].cnt += 1;
last = node;
continue;
}
int cur = nodes++;
T[cur].len = T[node].len + 2;
T[node].leg[now] = cur;
int link = T[node].link;
while (link != -1) {
if (now == str[i - T[link].len - 1] && T[link].leg.count(now)) {
link = T[link].leg[now];
break;
}
link = T[link].link;
}
if (link <= 0) link = 1;
T[cur].link = link;
T[cur].cnt = 1;
last = cur;
}
for (int node = nodes - 1; node > 0; --node)
{
T[T[node].link].cnt += T[node].cnt;
ans = max(ans, T[node].cnt * T[node].len);
}
}
};
main()
{
string s;
cin >> s;
PalTree arb(s);
cout << arb.ans << '\n';
}
Compilation message
palindrome.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
5 ms |
256 KB |
Output is correct |
| 7 |
Correct |
5 ms |
248 KB |
Output is correct |
| 8 |
Correct |
5 ms |
256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
380 KB |
Output is correct |
| 10 |
Correct |
5 ms |
364 KB |
Output is correct |
| 11 |
Correct |
5 ms |
256 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
256 KB |
Output is correct |
| 14 |
Correct |
5 ms |
256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
256 KB |
Output is correct |
| 17 |
Correct |
5 ms |
376 KB |
Output is correct |
| 18 |
Correct |
5 ms |
376 KB |
Output is correct |
| 19 |
Correct |
5 ms |
376 KB |
Output is correct |
| 20 |
Correct |
5 ms |
256 KB |
Output is correct |
| 21 |
Correct |
5 ms |
376 KB |
Output is correct |
| 22 |
Correct |
5 ms |
376 KB |
Output is correct |
| 23 |
Correct |
5 ms |
296 KB |
Output is correct |
| 24 |
Correct |
5 ms |
376 KB |
Output is correct |
| 25 |
Correct |
5 ms |
376 KB |
Output is correct |
| 26 |
Correct |
5 ms |
256 KB |
Output is correct |
| 27 |
Correct |
5 ms |
376 KB |
Output is correct |
| 28 |
Correct |
5 ms |
376 KB |
Output is correct |
| 29 |
Correct |
5 ms |
376 KB |
Output is correct |
| 30 |
Correct |
5 ms |
376 KB |
Output is correct |
| 31 |
Correct |
5 ms |
376 KB |
Output is correct |
| 32 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
504 KB |
Output is correct |
| 5 |
Correct |
5 ms |
504 KB |
Output is correct |
| 6 |
Correct |
5 ms |
504 KB |
Output is correct |
| 7 |
Correct |
5 ms |
504 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
6 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
13816 KB |
Output is correct |
| 2 |
Correct |
27 ms |
13816 KB |
Output is correct |
| 3 |
Correct |
27 ms |
13816 KB |
Output is correct |
| 4 |
Correct |
26 ms |
13816 KB |
Output is correct |
| 5 |
Correct |
26 ms |
13816 KB |
Output is correct |
| 6 |
Correct |
25 ms |
12152 KB |
Output is correct |
| 7 |
Correct |
25 ms |
12792 KB |
Output is correct |
| 8 |
Correct |
20 ms |
7672 KB |
Output is correct |
| 9 |
Correct |
21 ms |
8952 KB |
Output is correct |
| 10 |
Correct |
25 ms |
12792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
40852 KB |
Output is correct |
| 2 |
Correct |
71 ms |
40848 KB |
Output is correct |
| 3 |
Correct |
73 ms |
40852 KB |
Output is correct |
| 4 |
Correct |
66 ms |
40776 KB |
Output is correct |
| 5 |
Correct |
67 ms |
40852 KB |
Output is correct |
| 6 |
Correct |
65 ms |
38676 KB |
Output is correct |
| 7 |
Correct |
64 ms |
37652 KB |
Output is correct |
| 8 |
Correct |
56 ms |
22292 KB |
Output is correct |
| 9 |
Correct |
50 ms |
22164 KB |
Output is correct |
| 10 |
Correct |
61 ms |
37396 KB |
Output is correct |
| 11 |
Correct |
68 ms |
40852 KB |
Output is correct |
| 12 |
Correct |
51 ms |
23828 KB |
Output is correct |
