WA #3求助
查看原帖
WA #3求助
1030875
born_to_sun楼主2024/3/28 09:36
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n;
char a[N],b[N];
int ma[N];
int ans;
void manacher(){
	int mid=0,r=0;
	for(int i=1;i<=n*2+2;i++){
		int p=1;
		if(i<=r){
			p=min(r-i,ma[mid*2-i]);
		} 
		while(b[i-p]==b[i+p]){
			if(p%4==0){
				if(ma[i-p/2]==p/2){
					ans=max(ans,p);
				}
			}
			p++;
		}
		p--;
		ma[i]=p;
		if(i+p>r){
			r=i+p;
			mid=i;
		}
	}
}
int main(){
	cin>>n>>a+1;
	b[0]='^';
	b[1]='#';
	for(int i=1;i<=n;i++){
		b[i*2]=a[i];
		b[i*2+1]='#';
	}
	b[n*2+2]='?';
	manacher();
	cout<<ans;
	return 0;
}
2024/3/28 09:36
加载中...