萌新求助马拉车算法WA两个点
查看原帖
萌新求助马拉车算法WA两个点
316322
hzoi_liuchang楼主2020/7/23 14:00
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char s1[maxn],s[maxn];
int f[maxn];
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s",s1+1);
    s[0]='*';
    int cnt=2*n+1;
    for(int i=1;i<=cnt;i++){
        if(i&1) s[i]='%';
        else s[i]=s1[i/2];
    }
    int ans=0,mids=0,r=0;
    for(int i=1;i<=cnt;i+=2){
        if(i<=r) f[i]=min(f[2*mids-i],r-i+1);
        if(i<r && i-f[i]<mids) ans=max(ans,2*(i-mids));
        while(s[i+f[i]]==s[i-f[i]]) f[i]++;
        if(i+f[i]>r) r=i+f[i]-1,mids=i; 
    }
    printf("%d\n",ans);
    return 0;
}
2020/7/23 14:00
加载中...