C++14(g++5.4) 解法, 执行用时: 21ms, 内存消耗: 5580K, 提交时间: 2020-06-17 11:05:04

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=4e6+5;
char s[N],t[N];
int n,mr,mid,ans,r[N],f[N],g[N];
void manacher(char *t,int *f)
{
    r[0]=1;
    for(int i=1; i<=n; i++)
    {
        r[i]=0;
        if(i<mr)
            r[i]=min(r[mid*2-i],mr-i);
        while(t[i+r[i]]==t[i-r[i]]&&i-r[i]>=0)
            f[i+r[i]]=max(f[i+r[i]],r[i]+1),++r[i];
        if(i+r[i]>mr)
            mid=i,mr=i+r[i];
    }
}
int main()
{
    scanf("%s",s),n=strlen(s);
    for(int i=0; i<n; i++)
        t[i*2]='#',t[i*2+1]=s[i];
    t[n*2]='#',n<<=1;
    manacher(t,f),reverse(t,t+n+1),manacher(t,g);
    for(int i=1; i<=n; i++)
        f[i]=max(f[i],f[i-1]);
    for(int i=1; i<=n; i++)
        g[i]=max(g[i],g[i-1]);
    for(int i=1; i<n; i++)
    {
        if(i&1)
            ans=max(ans,f[i+1]+g[n-i-1]-2);
        else
            ans=max(ans,f[i]+g[n-i]-2);
    }
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 26ms, 内存消耗: 5752K, 提交时间: 2020-01-10 22:07:55

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
char s[N],t[N];
int n,mr,mid,ans,r[N],f[N],g[N];
void manacher(char *t,int *f){
    r[0]=1;
    for(int i=1;i<=n;i++){
        r[i]=0;
        if(i<mr)    r[i]=min(r[mid*2-i],mr-i);
        while(t[i+r[i]]==t[i-r[i]]&&i-r[i]>=0)
            f[i+r[i]]=max(f[i+r[i]],r[i]+1),++r[i];
        if(i+r[i]>mr)   mid=i,mr=i+r[i];
    }
}
int main(){
    scanf("%s",s),n=strlen(s);
    for(int i=0;i<n;i++)
        t[i*2]='#',t[i*2+1]=s[i];
    t[n*2]='#',n<<=1;
    manacher(t,f),reverse(t,t+n+1),manacher(t,g);
    for(int i=1;i<=n;i++)   f[i]=max(f[i],f[i-1]);
    for(int i=1;i<=n;i++)   g[i]=max(g[i],g[i-1]);
    for(int i=1;i<n;i++){
        if(i&1) ans=max(ans,f[i+1]+g[n-i-1]-2);
        else    ans=max(ans,f[i]+g[n-i]-2);
    }
    printf("%d\n",ans);
    return 0;
}