#include<bits/stdc++.h>
using namespace std;
const int nax = 3e5 + 3;
string s;
int n;
int len[nax], link[nax];
int tree[nax][26];
int occ[nax], t = 1;
int idx = 0;
long long ans = 0;
void extend(int p) {
while(s[p - len[t] - 1] != s[p]) t = link[t];
int x = link[t];
while(s[p - len[x] - 1] != s[p]) x = link[x];
int c = s[p] - 'a';
if(!tree[t][c]) {
tree[t][c] = ++idx;
len[idx] = len[t] + 2;
link[idx] = len[idx] == 1 ? 2 : tree[x][c];
} t = tree[t][c];
++occ[t];
}
void PlayGround() {
cin>>s;
n = s.size();
s = '#' + s; //1 based indexing (must for this implementation)
len[1] = -1, link[1] = 1; //odd len root
len[2] = 0, link[2] = 1; //even len root
t = idx = 2;
for(int i=1; i<=n; ++i) {
extend(i);
}
for(int i=idx; i>2; --i) {
ans = max(ans, len[i] * 1LL * occ[i]);
occ[link[i]] += occ[i];
}
cout<<ans<<'\n';
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
328 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
324 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
328 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
328 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
328 KB |
Output is correct |
| 32 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
456 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
456 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
328 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1108 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
11984 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11956 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11984 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11952 KB |
Output is correct |
| 5 |
Correct |
8 ms |
11952 KB |
Output is correct |
| 6 |
Correct |
6 ms |
8912 KB |
Output is correct |
| 7 |
Correct |
7 ms |
10192 KB |
Output is correct |
| 8 |
Correct |
2 ms |
720 KB |
Output is correct |
| 9 |
Correct |
3 ms |
3280 KB |
Output is correct |
| 10 |
Correct |
7 ms |
10192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
34988 KB |
Output is correct |
| 2 |
Correct |
22 ms |
34996 KB |
Output is correct |
| 3 |
Correct |
23 ms |
35056 KB |
Output is correct |
| 4 |
Correct |
22 ms |
35016 KB |
Output is correct |
| 5 |
Correct |
25 ms |
35016 KB |
Output is correct |
| 6 |
Correct |
20 ms |
31172 KB |
Output is correct |
| 7 |
Correct |
22 ms |
29348 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1244 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1244 KB |
Output is correct |
| 10 |
Correct |
19 ms |
28852 KB |
Output is correct |
| 11 |
Correct |
22 ms |
34992 KB |
Output is correct |
| 12 |
Correct |
8 ms |
4288 KB |
Output is correct |
