最长回文子串问题

顺序和逆序相同的字符串便是回文串（例如’aba’）。求一个字符串所有的子串中最长的回文串便是最长回文子串问题。

输入格式

仅1行，一个字符串，长度小于2000000

输出格式

仅1行，一个最长的回文子串

---

#include<bits/stdc++.h>
using namespace std;
#define zjj long long
const int N=131;
const int MAXN=3e6+5;
const zjj mod=1e9+9; 
int n,m;
zjj ans;
zjj x[MAXN],y[MAXN];
zjj p[MAXN];
string s;
zjj Lash(int l,int r){
	return ((y[r]-y[l+1]*p[l-r+1])%mod+mod)%mod;
}
zjj Hash(int l,int r){
	return ((x[r]-x[l-1]*p[r-l+1])%mod+mod)%mod;
}
bool check(int i,int mid){
	if(Hash(i-mid+1,i)==Lash(i+mid,i+1)) return true;
	return false;
//	cout<<"RE"<<endl;
}
pair<int,int> bbd;
int main(){
	cin>>s;
	n=s.length();
	s=" "+s;
	
	p[0]=1;//预处理
	for(int i=1;i<=n;i++){
		p[i]=p[i-1]*N%mod;
	}
	for(int i=1;i<=n;i++){//正序Hash
		x[i]=x[i-1]*N+s[i];
		x[i]%=mod;
	}
	for(int i=n;i>=1;i--){//逆序Hash
		y[i]=y[i+1]*N+s[i];
		y[i]%=mod;
	}
	
	for(int i=1;i<=n;i++){//二分查找最长的回文子串
		int l=1,r=min(i,n-i+1),idx=1;
		while(l<=r){
			int mid=(l+r)/2;
			if(Hash(i-mid+1,i)==Lash(i+mid-1,i)){
				l=mid+1;
				idx=mid;
			}
			else r=mid-1;
		}
		if(idx*2-1>=bbd.first){
			bbd={idx*2-1,i-idx+1};
		}

		l=0;
		r=min(i,n-i);
		idx=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(Hash(i-mid+1,i)==Lash(i+mid,i+1)){
				l=mid+1;
				idx=mid;
			}
			else r=mid-1;
		}
		if(idx*2-1>=bbd.first){
			bbd={idx*2,i-idx+1};
		}
	}
	for(int i=bbd.second;i<bbd.first+bbd.second;i++){
		cout<<s[i];
	}
	return 0;
}

只有91pts，不知道为啥错了。

被大数据卡掉了，实在看不出来... $QWQ$