社区讨论
为什么会t四个点
P3805【模板】Manacher参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo35l42b
- 此快照首次捕获于
- 2023/10/24 01:10 2 年前
- 此快照最后确认于
- 2023/10/24 01:10 2 年前
rt
CPP// Problem: P3805 【模板】manacher 算法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3805
// Memory Limit: 512 MB
// Time Limit: 500000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
char dt[22000002];
int p[22000002];
int cnt;
inline void get(){
char c=getchar();
dt[0]='~';
dt[1]='*';
cnt=1;
while(c<'a'||c>'z') c=getchar();
while(c>='a'&&c<='z') dt[++cnt]=c,dt[++cnt]='*',c=getchar();
}
int main(){
get();
// cout<<dt;
int ans=0;
for(int i=1;i<cnt;++i){
int r=0,mid=0;
if(i<r+mid){
p[i]=min(p[2*mid-i],r-i);
}
else p[i]=1;
while(dt[i-p[i]]==dt[i+p[i]]){
p[i]++;
}
if(i+p[i]>r){
r=i+p[i];
mid=i;
}
ans=max(ans,p[i]-1);
}
cout<<ans;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...