#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const int mx = 1e5+5, p = 5281, m1 = 1e9+7, m2 = 1e9+9;
int n, ans; string str;
pair<ll, ll> pPow[mx], hsh[2][mx];
int create[mx][26]; pair<int, int> destroy[mx];
//hsh is 1 indexed, getHash is inclusive, getReach is inclusive(0 means invalid)
pair<ll, ll> getHash(int l, int g, int rev){
l++; g++; int dir[2] = {-1, 1}; if (rev == 1) swap(l, g); l += dir[rev];
return {((hsh[rev][g].f-(hsh[rev][l].f*pPow[abs(g-l)].f)%m1)+m1)%m1,
((hsh[rev][g].s-(hsh[rev][l].s*pPow[abs(g-l)].s)%m2)+m2)%m2};
}
int getReach(int l, int r){
int low = 0, high = min(l+1, n-r);
while (low < high){
int mid = (low+high+1)/2;
if (getHash(l-mid+1, l, 0) == getHash(r, r+mid-1, 1)) low = mid;
else high = mid-1;
}
return low;
}
int main() {
cin >> str; n = str.size(); pPow[0] = {1, 1};
for (int i = 0; i < n; i++){
hsh[0][i+1] = {(hsh[0][i].f*p+(str[i]-'a'+1))%m1, (hsh[0][i].s*p+(str[i]-'a'+1))%m2};
hsh[1][n-i] = {(hsh[1][n-i+1].f*p+(str[n-i-1]-'a'+1))%m1, (hsh[1][n-i+1].s*p+(str[n-i-1]-'a'+1))%m2};
pPow[i+1] = {(pPow[i].f*p)%m1, (pPow[i].s*p)%m2};
}
for (int i = 0; i < n; i++){
for (int j = i; j < i+2; j++){
int r = getReach(i, j); ans += r;
if (i-r >= 0 and j+r <= n){
int add = 1+getReach(i-r-1, i+r+1);
create[i-r][str[i+r]-'a'] += add;
create[j+r][str[i-r]-'a'] += add;
}
if (r > 0){
destroy[i-r+1].f++; destroy[j+r].f++; destroy[j].f--; destroy[j+1].f--;
if (i == j) destroy[i].s -= r-1, destroy[i+1].s += r;
}
}
}
int change = 0, curr = 0, best = 0;
for (int i = 0; i < n; i++){
change += destroy[i].f; curr += change+destroy[i].s;
for (int j = 0; j < 26; j++){
best = max(best, create[i][j]-curr);
}
}
cout<<ans+best;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
16132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
