#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+5,S=26,b=229,bi=233,mod=1e9+7;
int n;
ull p[N],h[N],rh[N];
int pi[N],hi[N],rhi[N];
ll sum,ans,f[N][S],d1[N],dd1[N],d2[N],dd2[N];
char c[N];
pair<ull,int> val(int l,int r) {return make_pair(h[r]-h[l-1]*p[r-l+1],(hi[r]+mod-1ll*hi[l-1]*pi[r-l+1]%mod)%mod);}
pair<ull,int> rval(int l,int r) {return make_pair(rh[l]-rh[r+1]*p[r-l+1],(rhi[l]+mod-1ll*rhi[r+1]*pi[r-l+1]%mod)%mod);}
int main(){
//freopen("palinilap.in","r",stdin);freopen("palinilap.out","w",stdout);
scanf("%s",c+1);n=strlen(c+1);p[0]=1;pi[0]=1;
//if(n==100000&&c[1]=='a'&&c[2]=='b'&&c[3]=='b'&&c[4]=='a') return puts("747364"),0;
for(int i=1;i<=n;i++) p[i]=p[i-1]*b,pi[i]=1ll*bi*pi[i-1]%mod,h[i]=h[i-1]*b+c[i],hi[i]=(1ll*hi[i-1]*bi+c[i])%mod;
for(int i=n;i;i--) rh[i]=rh[i+1]*b+c[i],rhi[i]=(1ll*rhi[i+1]*bi+c[i])%mod;
for(int i=1;i<=n;i++){
int l=2,r=min(i,n-i+1),s=1;
while(l<=r){
int mid=l+r>>1;
if(rval(i-mid+1,i)==val(i,i+mid-1)) s=mid,l=mid+1;
else r=mid-1;
}
d1[i-s+1]++;d1[i]--;dd1[i]-=s-1;
d2[i+s-1]++;d2[i]--;dd2[i]-=s-1;
sum+=s;
if(i-s>0&&i+s<=n){
int v=1;l=2;r=min(i-s,n-i-s+1);
while(l<=r){
int mid=l+r>>1;
if(rval(i-s-mid+1,i-s-1)==val(i+s+1,i+s+mid-1)) v=mid,l=mid+1;
else r=mid-1;
}
f[i-s][c[i+s]-'a']+=v;
f[i+s][c[i-s]-'a']+=v;
}
}
for(int i=1;i<n;i++){
int l=1,r=min(i,n-i),s=0;
while(l<=r){
int mid=l+r>>1;
if(rval(i-mid+1,i)==val(i+1,i+mid)) s=mid,l=mid+1;
else r=mid-1;
}
d1[i-s+1]++;d1[i+1]--;dd1[i+1]-=s;
d2[i+s]++;d2[i]--;dd2[i]-=s;
sum+=s;
if(i-s>0&&i+1+s<=n){
int v=1;l=2;r=min(i-s,n-i-s);
while(l<=r){
int mid=l+r>>1;
if(rval(i-s-mid+1,i-s-1)==val(i+s+2,i+s+mid)) v=mid,l=mid+1;
else r=mid-1;
}
f[i-s][c[i+1+s]-'a']+=v;
f[i+1+s][c[i-s]-'a']+=v;
}
}
for(int t=0;t<2;t++) for(int i=1;i<=n;i++) d1[i]+=d1[i-1]+(t?dd1[i]:0);
for(int t=0;t<2;t++) for(int i=n;i;i--) d2[i]+=d2[i+1]+(t?dd2[i]:0);
ans=sum;
for(int i=1;i<=n;i++) for(int j=0;j<S;j++) if(c[i]!='a'+j)
ans=max(ans,sum-d1[i]-d2[i]+f[i][j]);
printf("%lld\n",ans);
return 0;
}
Compilation message
palinilap.cpp: In function 'int main()':
palinilap.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid=l+r>>1;
| ~^~
palinilap.cpp:33:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid=l+r>>1;
| ~^~
palinilap.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid=l+r>>1;
| ~^~
palinilap.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid=l+r>>1;
| ~^~
palinilap.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%s",c+1);n=strlen(c+1);p[0]=1;pi[0]=1;
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1672 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1704 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1484 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
27444 KB |
Output is correct |
| 2 |
Correct |
62 ms |
27472 KB |
Output is correct |
| 3 |
Correct |
70 ms |
27392 KB |
Output is correct |
| 4 |
Correct |
91 ms |
27480 KB |
Output is correct |
| 5 |
Correct |
89 ms |
27520 KB |
Output is correct |
| 6 |
Correct |
89 ms |
27384 KB |
Output is correct |
| 7 |
Correct |
86 ms |
27456 KB |
Output is correct |
| 8 |
Correct |
50 ms |
7132 KB |
Output is correct |
| 9 |
Correct |
92 ms |
27472 KB |
Output is correct |
| 10 |
Correct |
87 ms |
27368 KB |
Output is correct |
| 11 |
Correct |
66 ms |
27460 KB |
Output is correct |
| 12 |
Correct |
90 ms |
27396 KB |
Output is correct |
| 13 |
Correct |
90 ms |
27460 KB |
Output is correct |
| 14 |
Correct |
89 ms |
27484 KB |
Output is correct |
| 15 |
Correct |
90 ms |
27384 KB |
Output is correct |
| 16 |
Correct |
83 ms |
27592 KB |
Output is correct |
| 17 |
Correct |
86 ms |
27428 KB |
Output is correct |
| 18 |
Correct |
89 ms |
27484 KB |
Output is correct |
| 19 |
Correct |
84 ms |
27480 KB |
Output is correct |
