萌新92pts求助

wangjinbo @ 2020-12-01 20:04:20

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
char s[maxn<<1];
int f[maxn<<1];
int main()
{
    int n;
    scanf("%d",&n);
    s[0]='~';
    getchar();getchar();
    for(int i=1;i<=n;i++){
        scanf("%c",&s[2*i]);
        s[2*i-1]='|';
    }
    s[n=n*2+1]='|';
    //printf("%s\n",s);
    int mid=0,r=0,ans=0;
    for(int i=1;i<=n;i+=2){
        if(i<r)f[i]=min(f[mid*2-i],r-i);
        //printf("%d %d %d %d ",i,f[i],mid,r);
        if(i-f[i]<=mid)ans=max(ans,(i-mid)*2);
        while(s[i-f[i]-1]==s[i+f[i]+1])f[i]++;
        if(i+f[i]>r)mid=i,r=i+f[i];
        //printf("%d\n",f[i]);
    }
    printf("%d\n",ans);
    return 0;
}

by Lamorak @ 2021-10-05 09:42:50

@wangjinbo 我尝试了一下另外一种 manacher 版本，然后就 A 了

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
string s,a;
int f[maxn],mid,r,ans;
int main()
{
    int n;
    scanf("%d",&n);
    cin>>a;
    s="@#";
    for(int i=0;i<a.size();i++){
        s+=a[i];
        s+="#";
    }
    for(int i=1;i<s.size();i+=2){
        f[i] = r > i ? min(r - i, f[2 * mid - i]) : 1;
        while(s[i + f[i]] == s[i - f[i]]) f[i]++;
        if(r < i + f[i]){
            mid = i;
            r = i + f[i];
        }
        if(i - f[i] + 1 <= mid) ans = max(ans, 2 * (i - mid));
    }
    printf("%d\n",ans);
    return 0;
}

具体为什么我也说不上来，可能是 char 不稳定的原因