发现每个可行的答案是两个短的回文串拼成的一个长的回文串

所以短串一定是长串的某个后缀

建出来回文自动机后，在$fail$树$dfs$即可

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define N 500050 7 using namespace std; 8 int nxt[N],len[N],ch[N][26],cnt,last; 9 char s[N];10 void init(){11     nxt[0]=nxt[1]=1;12     len[1]=-1;cnt=1;13 }14 int getfail(int x,int en){15     while(s[en]!=s[en-len[x]-1])x=nxt[x];16     return x;17 }18 int e=1,head[N];19 struct edge{20     int v,next;21 }ed[N];22 void add(int u,int v){23     ed[e].v=v;24     ed[e].next=head[u];25     head[u]=e++;26 }27 int ans;28 int vis[N];29 void insert(int t,int en){30     int now=getfail(last,en);31     if(!ch[now][t]){32         int x=++cnt;33         len[x]=len[now]+2;34         int f=getfail(nxt[now],en);35         nxt[x]=ch[f][t];add(nxt[x],x);36         ch[now][t]=x;37     }38     last=ch[now][t];39 }40 void dfs(int x){41     if(len[x]%4==0&&vis[len[x]>>1])ans=max(ans,len[x]);42     vis[len[x]]++;43     for(int i=head[x];i;i=ed[i].next)44         dfs(ed[i].v);45     vis[len[x]]--;46 }47 int n;48 int main(){49     init();50     scanf("%d",&n);51     scanf("%s",s);52     for(int i=0;i