社区讨论
78pts求助!
P3805【模板】Manacher参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lp4vw7qj
- 此快照首次捕获于
- 2023/11/19 10:54 2 年前
- 此快照最后确认于
- 2023/11/19 11:35 2 年前
本机测的时候发现纯回文串(比如样例)过不了
但是普通的串(比如kirakanoisalaji)可以过
很奇怪……
代码:
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();
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...