求助~

P4287 [SHOI2011] 双倍回文

铃宕 @ 2019-05-10 21:30:40

为什么76,WA了3个点

#include<bits/stdc++.h>
using namespace std;
char a[11000020],s[22000020];
int l,mr,mid,ans=1,len[22000020];
void manacher(){
    for(int i=1;i<l;i++){
        if(i<mr) len[i]=min(len[mid*2-i],len[mid]+mid-i);
        else len[i]=1;
        while(s[i+len[i]]==s[i-len[i]]) len[i]++;
        if(len[i]+i>mr){
            mr=len[i]+i;
            mid=i;
        }
    }
}
void change(){
    s[0]=s[1]='#';
    for(int i=0;i<l;i++){
        s[i*2+2]=a[i];
        s[i*2+3]='#';
    }
    l=l*2+2,s[l]=0;
}
bool check(int i){
    if((len[i]-1)%4!=0)return false;
    if(len[i-(len[i]-1)/2]-1!=(len[i]-1)/2)return false;
    return true;
}
int main(){
    cin>>l;
    scanf("%s",a);
    change();
    manacher();
    for(int i=1;i<l;i++){
        /*ans=max(ans,len[i]);*/
        if(check(i)){
            ans=max(ans,len[i]);
            //cout<<len[i]<<" "<<i<<endl;
        }
    }
    printf("%d",ans-1);
}

by ferrum_cccp @ 2019-05-10 21:37:24

orz


|