萌新初学manacher,求助各位大佬 4TLE
查看原帖
萌新初学manacher,求助各位大佬 4TLE
807952
ybc2025chenyuyang楼主2023/8/9 17:42

rt

#include<bits/stdc++.h>
using namespace std;
#define MAX 11000005
int len,p[MAX<<1],k,ans;
char a[MAX],s[MAX<<1];
void manacher(){
    int r=0,c=0;
    for(int i=1;i<len;i++){
        if(i<r){
            p[i]=min(p[c<<1]-i,p[c]+c-i);
        }else{
            p[i]=1;
        }
        while(s[i+p[i]]==s[i-p[i]]){
            p[i]++;
        }
        if(p[i]+i<r){
            r=p[i]+i,c=i;
        }
    }
}
int main(){
    cin>>a;
    len=strlen(a);
    s[k++]='$',s[k++]='#';
    for(int i=0;i<len;i++){
        s[k++]=a[i],s[k++]='#';
    }
    s[k++]='&',len=k;
    manacher();
    for(int i=0;i<len;i++){
        ans=max(p[i],ans);
    }
    cout<<ans-1;
    return 0;
}
2023/8/9 17:42
加载中...