This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
using namespace std;
const int N=1e6+5;
const int MOD1=98765431;
const int MOD2=1000696969;
int n;
int ps1[N],ps2[N];
int PW1[N],PW2[N];
int ans[N];
string s;
const int M=31;
int pw(int a,int b,int MOD){
if(!b) return 1;
int rt=pw(a,b/2,MOD);
rt=(rt*rt)%MOD;
if(b&1) rt=(rt*a)%MOD;
return rt;
}
int inv(int x,int MOD){
return pw(x,MOD-2,MOD);
}
int f(int x){
if(ans[x]==-1){
int l=1+x;int r=n-x;
if(r==l) {ans[x]=1; return ans[x];}
else if(r<l) {ans[x]=0; return ans[x];}
else if((l+1)==r) {ans[x]=(s[l]==s[r])+1; return ans[x];}
ans[x]=0;
int t=-1;
while(1){
int mid1=(r+l)/2;
int mid2=mid1+1;
if((r-l+1)&1) mid1--;
FOR(i,0,mid1-l){
int hsh1m=ps1[i+l]-ps1[l-1];
hsh1m=hsh1m*inv(PW1[l-1],MOD1); hsh1m=((hsh1m%MOD1)+MOD1)%MOD1;
int hsh2m=ps1[r]-ps1[r-i-1];
hsh2m=hsh2m*inv(PW1[r-i-1],MOD1); hsh2m=((hsh2m%MOD1)+MOD1)%MOD1;
int hsh1p=ps2[i+l]-ps2[l-1];
hsh1p=hsh1p*inv(PW2[l-1],MOD2); hsh1p=((hsh1p%MOD2)+MOD2)%MOD2;
int hsh2p=ps2[r]-ps2[r-i-1];
hsh2p=hsh2p*inv(PW2[r-i-1],MOD2); hsh2p=((hsh2p%MOD2)+MOD2)%MOD2;
if(hsh1m==hsh2m&&hsh1p==hsh2p) {t=i; break;}
}
break;
}
if(t==-1) {
ans[x]=1;
return ans[x];
}else{
int mid1=(r+l)/2;
int mid2=mid1+1;
if((r-l+1)&1) mid1--;
FOR(i,t,min(mid1-l,2*t+3)){
int hsh1m=ps1[i+l]-ps1[l-1];
hsh1m=hsh1m*inv(PW1[l-1],MOD1); hsh1m=((hsh1m%MOD1)+MOD1)%MOD1;
int hsh2m=ps1[r]-ps1[r-i-1];
hsh2m=hsh2m*inv(PW1[r-i-1],MOD1); hsh2m=((hsh2m%MOD1)+MOD1)%MOD1;
int hsh1p=ps2[i+l]-ps2[l-1];
hsh1p=hsh1p*inv(PW2[l-1],MOD2); hsh1p=((hsh1p%MOD2)+MOD2)%MOD2;
int hsh2p=ps2[r]-ps2[r-i-1];
hsh2p=hsh2p*inv(PW2[r-i-1],MOD2); hsh2p=((hsh2p%MOD2)+MOD2)%MOD2;
if(hsh1m==hsh2m&&hsh1p==hsh2p) ans[x]=max(ans[x],f(x+i+1)+2);
}
}
}
return ans[x];
}
void Main(){
cin>>s; n=SZ(s); s='$'+s;
FOR(i,0,2*n) ans[i]=-1;
ps1[0]=0;
PW1[0]=1;
FOR(i,1,n) PW1[i]=(PW1[i-1]*M)%MOD1;
FOR(i,1,n){
ps1[i]=ps1[i-1];
ps1[i]+=((s[i]-'a'+1)*PW1[i-1])%MOD1;
}
ps2[0]=0;
PW2[0]=1;
FOR(i,1,n) PW2[i]=(PW2[i-1]*M)%MOD2;
FOR(i,1,n){
ps2[i]=ps2[i-1];
ps2[i]+=((s[i]-'a'+1)*PW2[i-1])%MOD2;
}
cout<<f(0)<<'\n';
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int T; cin>>T;
while(T--) Main();
return 0;
}
Compilation message (stderr)
palindromic.cpp: In function 'long long int f(long long int)':
palindromic.cpp:46:8: warning: unused variable 'mid2' [-Wunused-variable]
46 | int mid2=mid1+1;
| ^~~~
palindromic.cpp:68:8: warning: unused variable 'mid2' [-Wunused-variable]
68 | int mid2=mid1+1;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |