这都能超时
  • 板块题目总版
  • 楼主BLty777
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/15 09:23
  • 上次更新2025/1/15 14:12:37
查看原帖
这都能超时
1124954
BLty777楼主2025/1/15 09:23

P3805

#include<bits/stdc++.h>
using namespace std;
const int N=51000002;
int n,k,p[N<<1],ans=1;
char s[N],c[N<<1];
void change(){
	n=strlen(s),k=0;
	c[k++]='$',c[k++]='#';
	for(int i=0;i<n;i++){
		c[k++]=s[i];
		c[k++]='#';
	}
	c[k++]='&';
	n=k;
}
void Manacher(){
	int r=0,C;
	for(int i=1;i<n;i++){
		if(i<r) p[i]=min(p[(C<<1)-1],p[C]+C-i);
		else p[i]=1;
		while(c[i+p[i]]==c[i-p[i]]) p[i]++;
		if(p[i]+i>r){
			r=p[i]+i;
			C=i;
		}
	}
}
int main(){
	scanf("%s",&s);
	change();
	Manacher();
	for(int i=0;i<n;i++){
		ans=max(ans,p[i]);
	}
	printf("%d",ans-1);
	return 0;
}
2025/1/15 09:23
加载中...