C++(g++ 7.5.0) 解法, 执行用时: 8ms, 内存消耗: 3080K, 提交时间: 2023-07-23 20:15:18

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;
char s[N << 1],a[N];
int hw[N << 1],l[N << 1],r[N << 1],n;


void change()
{
    s[0] = s[1] = '#';
    for(int i = 0; i < n; i++) 
    {
        s[i * 2 + 2] = a[i];
        s[i * 2 + 3] = '#';
    }
    n = 2 * n + 2;
    s[n] = 0;
}

void manacher()
{
    int mid = 0,maxright = 0;
    for(int i = 1; i <= n; i++) 
    {
        if(i < maxright) hw[i] = min(hw[(mid << 1) - i],hw[mid] + mid - i);
        else hw[i] = 1;
        for(;s[i - hw[i]] == s[i + hw[i]]; hw[i]++);
        if(i + hw[i] > maxright) 
        {
            maxright = i + hw[i];
            mid = i;
        }
        r[i + hw[i] - 1] = max(r[i + hw[i] - 1],hw[i] - 1);
        l[i - hw[i] + 1] = max(l[i - hw[i] + 1],hw[i] - 1);
    }
}

int main()
{
    scanf("%s",a);
    n = strlen(a);
    change();
    manacher();
    for(int i = n - 2; i >= 1; i--) r[i] = max(r[i],r[i + 2] - 2);
    for(int i = 2; i <= n; i++) l[i] = max(l[i],l[i - 2] - 2);
    int ans = 0;
    for(int i = 1; i <= n; i++) if(l[i] && r[i]) ans = max(ans,l[i] + r[i]);
    cout << ans << endl;
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 10ms, 内存消耗: 3292K, 提交时间: 2023-02-01 20:40:21

//#只会是奇数，字母只会是偶数
//所以两者的长度都是减去1，没错了
#include <bits/stdc++.h>
using namespace std;
const int M=2e5+10;

int cnt=1;
char s[M];
int p[M],L[M],R[M];
void manacher(string t) {
    s[0]='@';
    s[1]='#';
    for(auto i:t)s[++cnt]=i,s[++cnt]='#';
    for(int i=1,mid=0,r=0;i<=cnt;i++) {
        if(i<=r)p[i]=min(p[2*mid-i],r-i+1);
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(i+p[i]>r)r=i+p[i]-1,mid=i;
        L[i+p[i]-1]=max(L[i+p[i]-1],p[i]-1);
        R[i-p[i]+1]=max(R[i-p[i]+1],p[i]-1);
    }
}

int main() {
    string t;cin>>t;
    manacher(t);
    for(int i=3;i<=cnt;i+=2)R[i]=max(R[i],R[i-2]-2);
    for(int i=cnt;i>=1;i-=2)L[i]=max(L[i],L[i+2]-2);
    int ans=0;
    for(int i=3;i<cnt;i++)ans=max(ans,L[i]+R[i]);
    cout<<ans;
    return 0;
}