RT,当输入为 eddeddbcbdbacdd 时,正确应输出 5 ,程序却输出 1 。求教
#include<bits/stdc++.h>
using namespace std;
string s;
#define BASE 511
#define N 11000010
typedef long long ll;
typedef unsigned long long ull;
ull ori[N];
ull rev[N];
ull mi[N];
void print(){
for(int i=0;i<s.size();i++) cout<<"ori["<<i<<"]="<<ori[i]<<' '; cout<<endl;
for(int i=0;i<s.size();i++) cout<<"rev["<<i<<"]="<<rev[i]<<' '; cout<<endl;
for(int i=0;i<s.size();i++) cout<<"mi["<<i<<"]="<<mi[i]<<' '; cout<<endl;
}
bool OK(ll x){//x 代表长度
if(x%2==1){
if(x==1) return true;
ll p=x/2;
for(ll i=0;i<s.size();i++) if(i-p>=0&&i+p<=s.size()-1){ //cout<<"E"<<endl;
ull s1=ori[i-1]-ori[i-p]*mi[p];
ull s2=rev[i+1]-rev[i+p]*mi[p];
// cout<<x<<":"<<s1<<' '<<s2<<endl;
if(s1==s2) return true;
}
return false;
}
else{
ll p=x/2;
for(ll i=0;i<s.size();i++) if(i-p+1>=0&&i+p<=s.size()-1){ //cout<<"E"<<endl;
ull s1=ori[i]-ori[i-p+1]*mi[p];
ull s2=rev[i+1]-rev[i+p]*mi[p];
// cout<<x<<":"<<s1<<' '<<s2<<endl;
if(s1==s2) return true;
}
return false;
}
}
int main(){
while(cin>>s){
ori[0]=s[0]-'a'; for(ll i=1;i<s.size();i++) ori[i]=ori[i-1]*BASE+s[i]-'a';
rev[s.size()-1]=s[s.size()-1]-'a'; for(ll i=s.size()-2;i>=0;i--) rev[i]=rev[i+1]*BASE+s[i]-'a';
mi[0]=1;
for(ll i=1;i<s.size();i++) mi[i]=mi[i-1]*BASE;
// print();
ll l=0,r=s.size();
ll ans1=l/*奇数*/,ans2=0;
while(l<=r){
ll mid=l+(r-l)/2;
if(OK(mid*2+1)){
l=mid+1;
ans1=mid*2+1;
}
else r=mid-1;
}
l=0,r=s.size();
while(l<=r){
ll mid=l+(r-l)/2;
if(OK(mid*2)){
l=mid+1;
ans2=mid*2;
}
else r=mid-1;
}
cout<<max(ans1,ans2)<<endl;
}
return 0;
/*
abcba
1 513 262144 133955584
1
513
262144
13
abba
*/
}
``