Luogu

分析

考虑建 PAM，对每个节点额外求出一个 $trans_u$ 表示长度 $\leq$ 当前节点长度一半的最长回文后缀。

这个直接从 $trans_{fa}$ 往上跳 $fail$ 直到跳到一个能扩展新加的字符且扩展后长度小于新节点一半的节点即可。

那么我们只需要判断 $len_{trans_u}$ 是否为偶数且 $len_u$ 是否等于 $len_{trans_u}$ 即可判断 $u$ 是不是一个双倍回文串。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n; char s[N];

int last,cnt;
int len[N],ch[N][26],fail[N],trans[N];
int getfail(int u,int i) {
    while (i-len[u]-1<0||s[i-len[u]-1]!=s[i]) u=fail[u];
    return u;
}
int gettrans(int u,int i) {
    while (i-len[u]-1<0||s[i-len[u]-1]!=s[i]||((len[u]+2)<<1)>len[cnt]) u=fail[u];
    return u;
}
void extend(char c,int i) {
    int p=getfail(last,i);
    if (!ch[p][c]) {
        ++cnt; len[cnt]=len[p]+2;
        fail[cnt]=ch[getfail(fail[p],i)][c],ch[p][c]=cnt;
        if (len[cnt]<=2) trans[cnt]=fail[cnt];
        else trans[cnt]=ch[gettrans(trans[p],i)][c];
    }
    last=ch[p][c];
}

int main() {
    n=read(); scanf("%s",s+1);
    fail[0]=1,len[1]=-1,cnt=1;
    for (int i=1;i<=n;++i) extend(s[i]-'a',i);
    int ans=0;
    for (int i=2;i<=cnt;++i)
        if (!(len[trans[i]]&1)&&(len[trans[i]]<<1)==len[i]) ans=max(ans,len[i]);
    printf("%d\n",ans);
    return 0;
}