#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 3e5 + 500;
const int INF = 0x3f3f3f3f;
const int ALP = 26;
struct node{
node *ch[ALP], *bk;
int len, cnt;
node() { len = 0, cnt = 0, bk = 0, memset(ch, 0, sizeof(ch)); }
node(int _len) { len = _len, cnt = 0, bk = 0, memset(ch, 0, sizeof(ch)); }
};
node *n0, *n1;
vector < node* > v;
node* create_eertree(string &s){
n0 = new node(0);
n1 = new node(-1);
n0->bk = n1; n1->bk = n1;
node* cur = n0;
for(int i = 0;i < (int)s.size();i++){
for(;cur->len+1>i||s[i-cur->len-1]!=s[i];cur=cur->bk);
node *rmb = cur->bk;
if(!cur->ch[s[i] - 'a'])
cur->ch[s[i] - 'a'] = new node(cur->len + 2), v.PB(cur->ch[s[i] - 'a']);
cur = cur->ch[s[i] - 'a']; cur->cnt++;
for(;rmb->len+1>i||s[i-rmb->len-1]!=s[i];rmb=rmb->bk);
if(cur->len == 1)
cur->bk = n0;
else{
if(!rmb->ch[s[i] - 'a'])
rmb->ch[s[i] - 'a'] = new node(rmb->len + 2), v.PB(rmb->ch[s[i] - 'a']);
cur->bk = rmb->ch[s[i] - 'a'];
}
}
return n0;
}
bool cmp(node* X, node* Y){
return X->len > Y->len;
}
string s;
void dfs(node* x) {
if(!x) return;
v.PB(x);
for(int i = 0;i < 26;i++)
if(x->ch[i]) dfs(x->ch[i]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> s;
ll mx = 0;
node* root = create_eertree(s);
//dfs(root); dfs(root->bk);
sort(v.begin(), v.end(), cmp);
for(int i = 0;i < (int)v.size();i++){
mx = max(mx, (ll)v[i]->len * v[i]->cnt);
v[i]->bk->cnt += v[i]->cnt;
}
cout << mx << endl;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:70:11: warning: unused variable 'root' [-Wunused-variable]
70 | node* root = create_eertree(s);
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
452 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
452 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
352 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
452 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
456 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
1 ms |
856 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2908 KB |
Output is correct |
2 |
Correct |
2 ms |
2908 KB |
Output is correct |
3 |
Correct |
2 ms |
2908 KB |
Output is correct |
4 |
Correct |
2 ms |
2908 KB |
Output is correct |
5 |
Correct |
3 ms |
2828 KB |
Output is correct |
6 |
Correct |
2 ms |
2908 KB |
Output is correct |
7 |
Correct |
2 ms |
2908 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
2140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24936 KB |
Output is correct |
2 |
Correct |
26 ms |
24784 KB |
Output is correct |
3 |
Correct |
19 ms |
24780 KB |
Output is correct |
4 |
Correct |
26 ms |
24784 KB |
Output is correct |
5 |
Correct |
25 ms |
24784 KB |
Output is correct |
6 |
Correct |
17 ms |
18268 KB |
Output is correct |
7 |
Correct |
18 ms |
20944 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
5 ms |
6104 KB |
Output is correct |
10 |
Correct |
18 ms |
21200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
75468 KB |
Output is correct |
2 |
Correct |
81 ms |
74436 KB |
Output is correct |
3 |
Correct |
69 ms |
73928 KB |
Output is correct |
4 |
Correct |
89 ms |
74640 KB |
Output is correct |
5 |
Correct |
91 ms |
73852 KB |
Output is correct |
6 |
Correct |
71 ms |
66768 KB |
Output is correct |
7 |
Correct |
66 ms |
61392 KB |
Output is correct |
8 |
Correct |
4 ms |
1248 KB |
Output is correct |
9 |
Correct |
4 ms |
1252 KB |
Output is correct |
10 |
Correct |
81 ms |
60624 KB |
Output is correct |
11 |
Correct |
68 ms |
73672 KB |
Output is correct |
12 |
Correct |
8 ms |
7908 KB |
Output is correct |