WA on #78 求条QWQ
查看原帖
WA on #78 求条QWQ
796137
ZZY_C2H5OH楼主2024/11/3 19:34
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
	return x;
}
void write(int x){
	static int sta[35];
	int top=0;
	do sta[top++]=x%10,x/=10;
	while(x);
	while(top) putchar(sta[--top]+'0');
}
const int N=4e5+10;
char c,s[N<<1];
int n,cnt,ans,p[N<<1];
signed main(){
	n=read(),s[0]='~',s[++cnt]='|';
	for(int i=n;i;i--) s[n*2-(++cnt)+2]=getchar(),s[++cnt]='|';
	for(int i=1,r=0,mid=0;i<=cnt;i++){
		if(i<=r) p[i]=min(p[(mid<<1)-i],r-i+1);
		while(s[i-p[i]]==s[i+p[i]]) p[i]++;
		if(p[i]+i>r) r=p[i]+i-1,mid=i;
		if(p[i]==i) ans=p[i]-1;
	}
	write(n-ans);
	return 0;
}
2024/11/3 19:34
加载中...