WA51,求调,玄关,快红温了
查看原帖
WA51,求调,玄关,快红温了
1077535
Lcm_simida楼主2025/1/12 15:59
#include<bits/stdc++.h>
using namespace std;
const unsigned long long N=1004535809,base=37;
string a;
unsigned long long n,f[100005],s[100005],pw[100005];
int L[100005],R[100005],ans=0;
bool check(int l,int r){
	if(l<1||l>n||r<1||r>n) return 0;
	unsigned long long cnt=((f[r]-f[l-1]*pw[r-l+1]%N)%N+N)%N;
	unsigned long long sum=((s[l]-s[r+1]*pw[r-l+1]%N)%N+N)%N;
	return cnt==sum;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>a;n=a.size();a=" "+a;
	pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*base%N,L[i]=R[i]=1;
	for(int i=1;i<=n;i++) f[i]=(((unsigned long long)f[i-1]*base+(a[i]-'a'+1))%N+N)%N;
	for(int i=n;i>=1;i--) s[i]=(((unsigned long long)s[i+1]*base+(a[i]-'a'+1))%N+N)%N;
	for(int i=1;i<=n;i++){
		int l=0,r=n+1;
		while(l+1<r){
			int mid=l+r>>1;
			if(check(i-mid,i+mid)) l=mid;
			else r=mid;
		}
		if(l!=0){
			L[i-l]=max(L[i-l],l*2+1),R[i+l]=max(R[i+l],l*2+1);
		}
		l=0,r=n+1;
		while(l+1<r){
			int mid=l+r>>1;
			if(check(i-mid+1,i+mid)) l=mid;
			else r=mid;
		}
		if(l!=0){
			L[i-l+1]=max(L[i-l+1],l*2),R[i+l]=max(R[i+l],l*2);
		}
	}
	for(int i=2;i<=n;i++) L[i]=max(L[i],L[i-1]-2);
	for(int i=n-1;i>=1;i--) R[i]=max(R[i],R[i+1]-2);
//	for(int i=1;i<=n;i++) cout<<L[i]<<" "<<R[i]<<"\n";
	for(int i=1;i<n;i++){
		ans=max(ans,R[i]+L[i+1]);
	}
	cout<<ans;
	return 0;
}
2025/1/12 15:59
加载中...