wa#5 求助
查看原帖
wa#5 求助
362627
frank15楼主2021/4/8 19:11
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=2e5+5;
int n,ans;
int l[maxn],r[maxn];
string a,s;
void init(){
	for(int i=0;i<a.size();i++){
		s+='#';
		s+=a[i];
	}
	s+='#';
	n=s.size();
}
void manacher(){
	int L=0,R=0;
	vector<int> d1;
	d1.resize(n);
	fill(d1.begin(),d1.end(),1);
	for(int i=0;i<n;i++){
		if(i<=R)
			d1[i]=min(d1[L+R-i],R-i+1);
		while(d1[i]<i+1&&i+d1[i]<n&&s[i-d1[i]]==s[i+d1[i]])
			++d1[i];
		
		if(i+d1[i]-1>R){
			L=i-d1[i]+1;
			R=i+d1[i]-1;
		}
		
		r[R]=max(r[R],d1[i]-1);
		l[L]=max(l[L],d1[i]-1);
	}
}
int main(){
	cin>>a;
	init();
	manacher();
	for(int i=0;i<n;i+=2)
		l[i]=max(l[i],l[i-2]-2);
	for(int i=n-1;i>=0;i-=2)
		r[i]=max(r[i],r[i+2]-2);
	for(int i=0;i<n;i+=2){
		if(l[i]&&r[i])
			ans=max(ans,l[i]+r[i]);
	}
	cout<<ans<<endl; 
}
2021/4/8 19:11
加载中...