#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const ll p2 = 179, mod2 = 993244853;
struct Hashing{
vector<ll> ha, ba;
ll p, mod;
Hashing(){ }
Hashing(char *s, ll p1, ll mod1) : p(p1), mod(mod1) {
int n = strlen(s);
ha.resize(n+1); ba.resize(n+1);
ba[0] = 1, ba[1] = p;
for(int i=n-1; i>=0; i--) ha[i] = (ha[i+1] * p + s[i]) % mod;
for(int i=2; i<=n; i++) ba[i] = ba[i-1] * p % mod;
}
int substr(int l, int r){
ll ret = ha[l] - ha[r+1] * ba[r-l+1];
ret %= mod; ret += mod; ret %= mod;
return ret;
}
} h2;
int n;
char s[606060];
int pal[606060];
vector<pi> v;
void manacher(){
for(int i=n-1; i>=0; i--){
s[i << 1 | 1] = s[i];
s[i << 1] = '#';
}
n <<= 1; s[n++] = '#';
int r = -1, p = -1;
for(int i=0; i<n; i++){
pal[i] = (i <= r ? min(pal[p*2-i], r-i) : 0);
while(i-pal[i]-1 >= 0 && i+pal[i]+1 < n && s[i-pal[i]-1] == s[i+pal[i]+1]) pal[i]++;
if(i+pal[i] > r) r = i+pal[i], p = i;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> s; n = strlen(s);
h2 = Hashing(s, p2, mod2);
manacher();
v.reserve(n/2);
for(int i=0; i<n; i++){
if(!pal[i]) continue;
if(i & 1){
for(int j=1; j<=pal[i]; j+=2){
int s = i/2 - j/2;
int e = i/2 + j/2;
v.emplace_back(h2.substr(s, e), e-s+1);
}
}else{
for(int j=2; j<=pal[i]; j+=2){
int s = i - j/2; s /= 2;
int e = i + j/2; e /= 2;
v.emplace_back(h2.substr(s, e), e-s+1);
}
}
}
ll ans = 0;
sort(all(v));
vector<pi> u = v;
v.erase(unique(all(v)), v.end());
for(auto i : v){
ll len = i.second;
ll cnt = upper_bound(all(u), i) - lower_bound(all(u), i);
ans = max(ans, len*cnt);
}
cout << ans;
}
# |
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 |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
380 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
4396 KB |
Output is correct |
2 |
Correct |
17 ms |
2328 KB |
Output is correct |
3 |
Incorrect |
57 ms |
8280 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
300 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
343 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
292 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |