WA on #5 求调
查看原帖
WA on #5 求调
1204974
adsd45666楼主2024/10/15 16:18

rt

#include<bits/stdc++.h>
#define seq(q,w,e) for(int q=w;q<=e;q++)
#define ll long long
using namespace std;
const int maxn=1e5+10;

char a[maxn],s[maxn<<2];
int n,p[maxn<<2],l[maxn<<2],r[maxn<<2];
int ans;
void in_it(){
	int k=0;
	s[k++]='$';
	s[k++]='#';
	for(int i=0;i<n;i++){
		s[k++]=a[i];
		s[k++]='#';
	}
	s[k++]='&';
	n=k-1;
}

void manacher(){
	int c,mr=0;
	for(int i=1;i<=n;i++){
		if(i<=mr) p[i]=min(p[(c<<1)-i],p[c]+c-i);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]]) p[i]++;
		if(p[i]+i>=mr){
			mr=p[i]+i;
			c=i;
		}
		r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1);
		l[i-p[i]+1]=max(l[i-p[i]+1],p[i]-1);
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>(a+1);
	n=strlen(a+1);
	in_it();
	manacher();
	for(int i=n;i>=1;i-=2) r[i]=max(r[i],r[i+2]-2);
	for(int i=1;i<=n;i+=2) l[i]=max(l[i],l[i-2]-2);
	for(int i=1;i<=n;i+=2) if(l[i]&&r[i]) ans=max(ans,l[i]+r[i]);
	cout<<ans;
	return 0;
}
2024/10/15 16:18
加载中...