sol
首先求出以每个位置结尾的最长回文后缀长度。
然后你实际上就是要求：对于一个长度为\(4\)的倍数的回文子串，是否存在一个长度为他的一半的回文后缀。
这个可以沿后缀树\(dfs\)一遍。因为一个回文子串的所有回文后缀一定都是他在回文树上的祖先。
code
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5e5+5;
int last,tot,tr[N][26],fa[N],len[N],to[N],nxt[N],head[N],cnt,vis[N],ans;
char s[N];
void link(int u,int v)
{
to[++cnt]=v;nxt[cnt]=head[u];
head[u]=cnt;
}
void init()
{
fa[0]=fa[1]=1;len[tot=1]=-1;
link(1,0);
}
void extend(int c,int n)
{
int v=last;
while (s[n-len[v]-1]!=s[n]) v=fa[v];
if (!tr[v][c])
{
int u=++tot,k=fa[v];
len[u]=len[v]+2;
while (s[n-len[k]-1]!=s[n]) k=fa[k];
fa[u]=tr[k][c];tr[v][c]=u;
link(fa[u],u);
}
last=tr[v][c];
}
void dfs(int u)
{
if (len[u]%4==0&&vis[len[u]/2]) ans=max(ans,len[u]);
++vis[len[u]];
for (int e=head[u];e;e=nxt[e]) dfs(to[e]);
--vis[len[u]];
}
int main()
{
int n;scanf("%d",&n);
scanf("%s",s+1);
init();
for (int i=1;i<=n;++i) extend(s[i]-'a',i);
dfs(1);
printf("%d\n",ans);return 0;
}