#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mem(x, y) memset(& x, y, sizeof(x))
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
using namespace std;
const int n0=1e5+123;
int n;
string s;
namespace Hash {
const array<int,2> mod={(int)1e9+7,(int)1e9+9};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int base=uniform_int_distribution<int>(27,(int)1e9)(rng);
struct mint {
array<int,2> x;
mint(int val=0) {
x[0]=x[1]=val;
}
void operator *= (const mint &a) {
x[0]=(ll)x[0]*a.x[0]%mod[0];
x[1]=(ll)x[1]*a.x[1]%mod[1];
}
void operator += (const mint &a) {
x[0]+=a.x[0];if(x[0]>=mod[0]) x[0]-=mod[0];
x[1]+=a.x[1];if(x[1]>=mod[1]) x[1]-=mod[1];
}
void operator -= (const mint &a) {
x[0]-=a.x[0];if(x[0]<0) x[0]+=mod[0];
x[1]-=a.x[1];if(x[1]<0) x[1]+=mod[1];
}
mint operator * (const mint &a) {
mint res=*this;
res*=a;
return res;
}
mint operator + (const mint &a) {
mint res=*this;
res+=a;
return res;
}
mint operator - (const mint &a) {
mint res=*this;
res-=a;
return res;
}
bool operator == (const mint &a) {
return x[0]==a.x[0] && x[1]==a.x[1];
}
};
mint pref[n0],suf[n0],pw[n0];
void build() {
pw[0]=1;
for(int i=1; i<=n; i++) {
pw[i]=pw[i-1]*base;
pref[i]=pref[i-1]+pw[i]*(s[i-1]-'a'+1);
}
for(int i=n; i>=1; i--) {
suf[i]=suf[i+1]+pw[n-i+1]*(s[i-1]-'a'+1);
}
};
mint get(int l,int r) {
return pw[n-r]*(pref[r]-pref[l-1]);
}
mint get_rev(int l,int r) {
return pw[l-1]*(suf[l]-suf[r+1]);
}
}
bool pal(int l,int r,int l2,int r2) {
if(l<1 || l2<1 || r>n || r2>n) return 0;
return Hash::get(l,r)==Hash::get_rev(l2,r2);
}
int find(int L,int R) {
int l=-1,r=n;
while(l<r-1) {
int mid=l+r>>1;
if(pal(L-mid,L,R,R+mid)) l=mid;
else r=mid;
}
return l;
}
ll mul[n0],add[n0];
void add_inc(int l,int r,int x) {
//(x-l)+i
add[l]+=x-l,add[r+1]-=x-l;
mul[l]++,mul[r+1]--;
}
void add_dec(int l,int r,int x) {
//(x+l)-i
add[l]+=x+l,add[r+1]-=x+l;
mul[l]--,mul[r+1]++;
}
ll get(int pos) {
return add[pos]+mul[pos]*pos;
}
ll positive[n0][26],init;
void process(int L,int R) {
int a=find(L,R);
init+=a+1;
int b=find(L-a-2,R+a+2);
if(L-a-1>=1 && R+a+1<=n) {
positive[L-a-1][s[R+a]-'a']+=1+(b+1);
positive[R+a+1][s[L-a-2]-'a']+=1+(b+1);
}
if(a>=0) {
add_inc(L-a,L,-a-1);
add_dec(R,R+a,-1);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> s;n=SZ(s);
Hash::build();
for(int i=1; i<=n-1; i++) process(i,i+1);
for(int i=1; i<=n-2; i++) process(i,i+2);
ll ans=init;
for(int i=1; i<=n; i++) {
add[i]+=add[i-1];
mul[i]+=mul[i-1];
ll diff=get(i);
ll cur=0;
for(int j=0; j<26; j++) {
cur=0;
if(s[i-1]-'a'!=j) cur+=diff;
cur+=positive[i][j];
ans=max(ans,init+cur);
}
}
cout << ans+n;
}
Compilation message
palinilap.cpp: In function 'int find(int, int)':
palinilap.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3820 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
3840 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
25068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
