为什么除了前三个点都TLE了
查看原帖
为什么除了前三个点都TLE了
658497
letianJOE楼主2024/2/24 08:54
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 1e7;
int n;
int ans=-1;
int p[2*N+5];
char a[2*N+5];
char s[2*N+5];
void manacher()
{
	int r=1,c=1;
	for(int i=1;i<n;i++)
	{
		p[i]=(i<r)?min(p[c*2-i],r-i):1;
		while(s[i+p[i]]==s[i-p[i]])
			p[i]++;
		if(p[i]+i>r)
			r=p[i]+i,c=i;	
	}	
}
void input()
{
	cin>>a;
	s[n++]='@',s[n++]='#';
	for(int i=0;i<strlen(a);i++)
		s[n++]=a[i],s[n++]='#';
	s[n]='$';
}
main()
{
	input();
//	cout<<s<<endl;
	manacher();
//	for(int i = 0;i<n;i++)cout<<p[i]<<" ";
//	cout<<endl;
	for(int i=0;i<n;i++)
		ans=max(ans,p[i]-1);
	cout<<ans<<"\n";
	return 0;
}
2024/2/24 08:54
加载中...