#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define MP make_pair
#define pii pair<int, int>
#define int long long
using namespace std;
const ll MX=2e5+5, del=1e9+7;
ll n, p=29, pbase[MX], h1[MX], h2[MX], arr[MX], ans[MX], ps[MX], cnt[MX], ANS, yek=1;
string s;
vector<pii>vec;
void HASH(){
for(int i=1;i<=n;i++) h1[i]=(h1[i-1]*p+arr[i])%del;
for(int i=n;i>=1;i--) h2[i]=(h2[i+1]*p+arr[i])%del;
}
int gethash(int l, int r, bool tp){
int ans=0;
if(tp==0){
ans=(h1[r]-(pbase[r-l+1]*h1[l-1]%del)+del)%del;
}
else{
ans=(h2[l]-(pbase[r-l+1]*h2[r+1]%del)+del)%del;
}
return ans;
}
bool ispal(int l, int r){
if(l>=r) return true;
if(l<=0 || l>n) return false;
if(gethash(l, r, 0)==gethash(l, r, 1)) return true;
return false;
}
bool ispal2(int l, int r, int R){
if(l>=r) return true;
if(l<=0 || l>n) return false;
if(gethash(l, r, 0)==gethash(R, R+(l-r), 1)) return true;
return false;
}
int32_t main(){
pbase[0]=1;
for(int i=1;i<MX;i++){
pbase[i]=pbase[i-1]*p%del;
}
cin>>s;
n=s.size();
for(int i=0;i<n;i++){
arr[i+1]=s[i]-'a'+1;
}
HASH();
//cout<<ispal(2, 6)<<endl;
for(int i=2;i<=2*n;i++){
int lo=-1, hi=2*MX;
while(hi-lo>1){
int mid=(hi+lo)/2;
//cout<<mid<<" "<<i-mid<<" "<<ispal(mid, i-mid)<<endl;
if(ispal(mid, i-mid)){
hi=mid;
}
else{
lo=mid;
}
}
//cout<<i<<" "<<hi<<endl;
int l=hi, r=i-hi;
if(r>=l) ANS+=(r-l)/2+1;
if(r>=l) vec.pb(MP(l, r));
if(l==1 || r==n) continue;
if(l==2 || r==n-1){
if(ans[l-1]==0) ans[l-1]=1;
if(ans[r+1]==0) ans[r+1]=1;
continue;
}
if(arr[l-2]!=arr[r+2]){
if(ans[l-1]==0) ans[l-1]=1;
if(ans[r+1]==0) ans[r+1]=1;
continue;
}
lo=-1, hi=2*MX;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(ispal2(mid, l-2, r+2)){
hi=mid;
}
else{
lo=mid;
}
}
int temp=l-hi;
ans[l-1]=max(ans[l-1], temp), ans[r+1]=max(ans[r+1], temp);
}
//cout<<ANS<<endl;
//cout<<ans[2]<<endl;
for(int i=0;i<vec.size();i++){
int l=vec[i].F, r=vec[i].S;
cnt[l]++, cnt[r+1]--;
ps[l]+=l-1;
ps[r+1]-=(l-1);
}
int sum=0;
int TANS=ANS;
for(int i=1;i<=n;i++){
sum+=ps[i];
ANS=max(ANS, TANS+ans[i]-cnt[i]*i-sum+1);
}
cout<<ANS<<endl;
return 0;
}
Compilation message
palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:105:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec.size();i++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
9392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
