# include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 2;
int n, bor[26][N], cnt[N * 27], cn = 1;
long long ans;
string s;
void add(int id, int c){
int v = 1;
for(int len = 0; len < min(n - id + 1, id); len ++){
if(id - len <= 0 || id + len + c > n || s[id - len] != s[id + len + c]){
break;
}
int now = s[id - len] - 'a';
if(!bor[now][v]){
bor[now][v] = ++ cn;
}
v = bor[now][v];
}
cnt[v] ++;
}
void f(int v, int len, int c){
for(int i = 0; i < 26; i ++){
if(bor[i][v]){
f(bor[i][v], len + 1, c);
cnt[v] += cnt[ bor[i][v] ];
}
}
ans = max(ans, (len * 2 - c - 2) *1ll* cnt[v]);
}
int main(){
cin >> s;
n = s.size();
s = ' ' + s;
for(int i = 1; i <= n; i ++){
add(i, 0);
}
f(1, 1, 1);
cn = 1;
memset(bor, 0, sizeof(bor));
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i < n; i ++){
if(s[i] == s[i + 1])
add(i, 1);
}
f(1, 1, 0);
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2432 KB |
Output is correct |
2 |
Correct |
4 ms |
2432 KB |
Output is correct |
3 |
Correct |
4 ms |
2432 KB |
Output is correct |
4 |
Correct |
4 ms |
2432 KB |
Output is correct |
5 |
Correct |
4 ms |
2432 KB |
Output is correct |
6 |
Correct |
4 ms |
2432 KB |
Output is correct |
7 |
Correct |
4 ms |
2432 KB |
Output is correct |
8 |
Correct |
4 ms |
2432 KB |
Output is correct |
9 |
Correct |
4 ms |
2432 KB |
Output is correct |
10 |
Correct |
4 ms |
2432 KB |
Output is correct |
11 |
Correct |
4 ms |
2432 KB |
Output is correct |
12 |
Correct |
4 ms |
2432 KB |
Output is correct |
13 |
Correct |
4 ms |
2432 KB |
Output is correct |
14 |
Correct |
4 ms |
2432 KB |
Output is correct |
15 |
Correct |
5 ms |
2432 KB |
Output is correct |
16 |
Correct |
2 ms |
2432 KB |
Output is correct |
17 |
Correct |
4 ms |
2432 KB |
Output is correct |
18 |
Correct |
4 ms |
2432 KB |
Output is correct |
19 |
Correct |
5 ms |
2432 KB |
Output is correct |
20 |
Correct |
5 ms |
2432 KB |
Output is correct |
21 |
Correct |
2 ms |
2432 KB |
Output is correct |
22 |
Correct |
4 ms |
2432 KB |
Output is correct |
23 |
Correct |
4 ms |
2432 KB |
Output is correct |
24 |
Correct |
4 ms |
2432 KB |
Output is correct |
25 |
Correct |
5 ms |
2432 KB |
Output is correct |
26 |
Correct |
4 ms |
2432 KB |
Output is correct |
27 |
Correct |
5 ms |
2432 KB |
Output is correct |
28 |
Correct |
4 ms |
2432 KB |
Output is correct |
29 |
Correct |
4 ms |
2432 KB |
Output is correct |
30 |
Correct |
4 ms |
2432 KB |
Output is correct |
31 |
Correct |
4 ms |
2432 KB |
Output is correct |
32 |
Correct |
5 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2432 KB |
Output is correct |
2 |
Correct |
4 ms |
2432 KB |
Output is correct |
3 |
Correct |
6 ms |
2432 KB |
Output is correct |
4 |
Correct |
4 ms |
2432 KB |
Output is correct |
5 |
Correct |
6 ms |
2432 KB |
Output is correct |
6 |
Correct |
6 ms |
2432 KB |
Output is correct |
7 |
Correct |
4 ms |
2432 KB |
Output is correct |
8 |
Correct |
5 ms |
2432 KB |
Output is correct |
9 |
Correct |
3 ms |
2432 KB |
Output is correct |
10 |
Correct |
5 ms |
2432 KB |
Output is correct |
11 |
Correct |
4 ms |
2432 KB |
Output is correct |
12 |
Correct |
5 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
2732 KB |
Output is correct |
2 |
Correct |
56 ms |
2652 KB |
Output is correct |
3 |
Correct |
146 ms |
2780 KB |
Output is correct |
4 |
Correct |
110 ms |
2680 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
19 ms |
2560 KB |
Output is correct |
8 |
Correct |
5 ms |
2432 KB |
Output is correct |
9 |
Correct |
5 ms |
2432 KB |
Output is correct |
10 |
Correct |
5 ms |
2560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1068 ms |
1232 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1051 ms |
1800 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |