社区讨论

求助

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 条回复,欢迎继续交流。

正在加载回复...