社区讨论

78pts求助!

P3805【模板】Manacher参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lp48abkt
此快照首次捕获于
2023/11/18 23:53
2 年前
此快照最后确认于
2023/11/19 08:46
2 年前
查看原帖
#4 TLE,#8 #16 WA
这是代码:
CPP
#include<bits/stdc++.h>
using namespace std;
int n,p[22000002];
char s[11000002],t[22000003];
void manacher() {
	n=strlen(s+1);
	int m=0;
	t[++m]='$';
	for(int i=1; i<=n; i++)
		t[++m]=s[i],t[++m]='$';
	int M=0,R=0;
	for(int i=1; i<=m; i++) {
		if(i>R)
			p[i]=1;
		else
			p[i]=min(p[2*M-i],R-i+1);
		while(i-p[i]>0 and i+p[i]<=m and t[i-p[i]]==t[i+p[i]])
			++p[i];
		if(i+p[i]-1>R)
			M=i;
			R=i+p[i]-1;
	}
	int ans=0;
	for(int i=1; i<=m; i++) {
		ans=max(ans,p[i]);
	}
	printf("%d\n",ans-1);
}
int main(){
	scanf("%s",s);
	manacher();
}
PS:本机测的时候发现,如果输入的字符串就是回文串(如aaa、abdbdba),结果不正确
很好奇为什么……明明其他情况是对的
这么晚发帖真的会有人看吗

回复

1 条回复,欢迎继续交流。

正在加载回复...