社区讨论
在循环内求解和循环外求有什么区别啊
P3805【模板】Manacher参与者 2已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @mi6z4muc
- 此快照首次捕获于
- 2025/11/20 13:11 4 个月前
- 此快照最后确认于
- 2025/11/20 15:41 4 个月前
用注释掉的那条代码就全WA了
但是我觉得没啥区别啊
CPP#include <bits/stdc++.h>
#define inf 22000001
using namespace std;
char a[inf],s[inf];
int len,ans=1;
int p[inf];
void change( ){
int j=2;
s[0]=s[1]='$';
for(register int i=0;i<len;i++){
s[j]=a[i];j++;
s[j]='$';j++;
}
s[j]='&';
len=j;
return ;
}
void manacher( ){
int maxright=1,mid=1;
for(register int i=1;i<len;i++)
{
if(i<maxright) p[i]=min(maxright-i,p[mid*2-i]);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(maxright<i+p[i]){
mid=i;
maxright=i+p[i];
}
ans=max(ans,p[i]);
return ;
}
int main( ){
scanf("%s",a);
len=strlen(a);
change( );
manacher( );
//for(register int i=0;i<len;i++) {ans=max(ans,p[i]);}
printf("%d",ans-1);
return 0;
}
回复
共 15 条回复,欢迎继续交流。
正在加载回复...