#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(int _len = 0) { 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);
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);
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 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 |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 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 |
596 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 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 |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 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 |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3164 KB |
Output is correct |
2 |
Correct |
2 ms |
2908 KB |
Output is correct |
3 |
Correct |
3 ms |
3164 KB |
Output is correct |
4 |
Correct |
3 ms |
3160 KB |
Output is correct |
5 |
Correct |
2 ms |
2908 KB |
Output is correct |
6 |
Correct |
3 ms |
2904 KB |
Output is correct |
7 |
Correct |
2 ms |
2908 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
2136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
26580 KB |
Output is correct |
2 |
Correct |
34 ms |
25812 KB |
Output is correct |
3 |
Correct |
45 ms |
26580 KB |
Output is correct |
4 |
Correct |
42 ms |
25992 KB |
Output is correct |
5 |
Correct |
31 ms |
26068 KB |
Output is correct |
6 |
Correct |
21 ms |
19160 KB |
Output is correct |
7 |
Correct |
35 ms |
21700 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
10 ms |
6748 KB |
Output is correct |
10 |
Correct |
25 ms |
22488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
260 ms |
81168 KB |
Output is correct |
2 |
Correct |
137 ms |
76980 KB |
Output is correct |
3 |
Correct |
193 ms |
81196 KB |
Output is correct |
4 |
Correct |
119 ms |
79052 KB |
Output is correct |
5 |
Correct |
127 ms |
81316 KB |
Output is correct |
6 |
Correct |
98 ms |
70720 KB |
Output is correct |
7 |
Correct |
97 ms |
62432 KB |
Output is correct |
8 |
Correct |
4 ms |
996 KB |
Output is correct |
9 |
Correct |
4 ms |
1152 KB |
Output is correct |
10 |
Correct |
115 ms |
64652 KB |
Output is correct |
11 |
Correct |
244 ms |
80816 KB |
Output is correct |
12 |
Correct |
11 ms |
8160 KB |
Output is correct |