听说有大佬用manacher$O(n)$过此题……太强啦……

说一下PAM的做法吧。（看了题解之后发现）蛮简单的

我们肯定要先建出回文自动机的

然后如果是枚举每一个节点暴跳fail指针肯定得T

那么我们对于每一个节点记录一个$trans[i]$，表示小于等于它长度一半的节点

这个可以在建自动机的时候顺便求出来，具体看代码

然后对每一个节点判断长度是否模4为0且$trans[i]$的长度是它的一半就好了

1 //minamoto 2 #include
     
       3 #include
      
        4 template
       
        inline bool cmax(T&a,const T&b){
   return a
        
         len[q]) tmp=fail[tmp];27                 trans[q]=ch[tmp][x];28             }29         }30         cnt[last=ch[p][x]]++;31     }32 }33 int main(){34 //    freopen("testdata.in","r",stdin);35     scanf("%d",&n);36     scanf("%s",s+1);37     s[0]=-1,fail[0]=1,last=0;38     len[0]=0,len[1]=-1,tot=1;39     build();40     for(int i=tot;i>=2;--i) cnt[fail[i]]+=cnt[i];41     for(int i=2;i<=tot;++i)42     if((len[trans[i]]<<1)==len[i]&&len[i]%4==0) cmax(ans,len[i]);43     printf("%d\n",ans);44     return 0;45 }