社区讨论
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 条回复,欢迎继续交流。
正在加载回复...