求最长回文子串
  • 板块学术版
  • 楼主VickeyTugan
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/7/2 10:10
  • 上次更新2023/11/4 20:26:01
查看原帖
求最长回文子串
343733
VickeyTugan楼主2021/7/2 10:10

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
*/
} 
``
2021/7/2 10:10
加载中...