#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector
using T = __int128;
ll mod = (1LL<<61)-1, b = 5;
ll mul(ll a, ll b) {return (__int128)a*b%mod;}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
string s; cin >> s;
int n = s.size();
s = '0'+s;
v<T> fac(n+1,0), hsh(n+1,0), hsh2(n+2,0);
fac[0] = 1;
for (int i=0;i<n;i++) {
fac[i+1] = fac[i]*b%mod;
hsh[i+1] = ((fac[i]*(s[i+1]-'a'+1)%mod)+hsh[i])%mod;
hsh2[n-i] = ((fac[i]*(s[n-i]-'a'+1)%mod)+hsh2[n-i+1])%mod;
}
auto check = [&](int l1, int r1, int l2, int r2) { // compare strings [l1,r1], [r2,l2]
int p1 = l1, p2 = n-l2+1;
T h1 = (hsh[r1]-hsh[l1-1]+mod)%mod, h2 = (hsh2[r2]-hsh2[l2+1]+mod)%mod;
//cout<<(ll)h1<<' '<<(ll)h2<<'\n';
if (p1<p2) {h1 = mul(h1,fac[p2-p1]);}
else {h2 = mul(h2,fac[p1-p2]);}
return (h1==h2);
};
v<v<ll>> change(n+1,v<ll>(26,0));
v<ll> ps(n+3,0), pal(n+1);
ll tot = 0;
//cout <<check(1,6,7,12)<<'\n';
//cout<<check(n-1,n,3,2) << '\n';
//cout<<check(3,4,2,1)<<'\n';
//cout<<hsh[2]<<' ' <<
auto calc = [&](int i1, int i2, int doit) {
int l = 0, h = min(i1-1,n-i2), m = (l+h)/2, ans;
while (l <= h) {
if (check(i2+1,i2+m,i1-1,i1-m)) {
l = m+1;
ans = m;
} else {h = m-1;}
m = (l+h)/2;
}
if (doit) {return ans;}
// update prefix sum
if (i1==i2) {pal[i1] += ans+1;}
ps[i1-ans]++;
ps[i1+1]--;
ps[i2+1]--;
ps[i2+ans+2]++;
tot += ans+1;
//cout<<i1<<' '<<i2<<' '<<ans+1<<'\n';
if (ans!=min(i1-1,n-i2)) {
l = ans+2, h = min(i1-1,n-i2), m = (l+h)/2; int ans2 = 0;
while (l <= h) {
if (check(i2+ans+2,i2+m,i1-ans-2,i1-m)) {
l = m+1;
ans2 = m-(ans+1);
} else {h = m-1;}
m = (l+h)/2;
}
change[i1-ans-1][s[i2+ans+1]-'a'] += ans2+1;
change[i2+ans+1][s[i1-ans-1]-'a'] += ans2+1;
}
return 0;
};
for (int i=1;i<=n;i++) {
calc(i,i,0);
if (i<n) {
if (s[i]==s[i+1]) {calc(i,i+1,0);}
else {
int z = calc(i,i+1,1)+1;
change[i][s[i+1]-'a'] += z;
change[i+1][s[i]-'a'] += z;
}
}
}
//return 0;
ll ans = tot;
for (int i=1;i<=n;i++) {
ps[i+1] += ps[i];
}
for (int i=1;i<=n;i++) {
ps[i+1] += ps[i];
ps[i] -= pal[i];
ll add = 0;
for (int j=0;j<26;j++) {add = max(add,change[i][j]);}
ans = max(ans,tot-ps[i]+add);
}
cout << ans << '\n';
// run prefix sum
// calculate answer
/*
calc number palindromes total!
find number centered at each character with bin search/string hashing
next, find num palindromes going through an index such that the index
is not the center (because then, modifying that index will 100% delete
all these palindromes)
do this with double prefix sum
next, we need to calculate number palindromes gained by changing an index
to a character
we basically calc palindromes but 1 mismatch allowed, so when calc
total from each center, find the first mismatch, rectify it, then continue
further, and store for those mismatched indices how many palindromes can
be gained if we change to the other letter
and so, go through each index/letter combo and subtract/add accordingly
*/
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |