社区讨论
求助
P3805【模板】Manacher参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi4re6s1
- 此快照首次捕获于
- 2025/11/18 23:59 3 个月前
- 此快照最后确认于
- 2025/11/20 04:04 3 个月前
最近在备考 NOIP,但是蒟蒻太菜了,马拉车都不会,TLE 18pts,求调。
CPP#include <bits/stdc++.h>
using namespace std;
char b[11000005],a[22000005];
int p[22000005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>b;
a[0]='^',a[1]='#';
int pp=2;
for(int i=0;i<strlen(b);i++){
a[pp]=b[i],a[pp+1]='#';
pp+=2;
}
a[pp]='$',a[pp+1]='\0';
int c=0,r=0,ans=0,len=strlen(a);
for(int i=1;i<len;i++){
if(i<r){
int i_mirror=2*c-i;
p[i]=min(r-i,p[i_mirror]);
}
while(a[i+(p[i]+1)]==a[i-(p[i]+1)]){
p[i]++;
}
if(i+p[i]>r){
c=i,r=i+p[i];
}
ans=max(ans,p[i]);
}
cout<<ans;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...