题意

思路

好像还是回文自动机裸体，但是 \(\text{Manacher}\) +后缀自动机+倍增也可以解决。

首先可以一遍 \(\text{Manacher}\) 得到本质不同的回文串，然后分别求一次出现次数，更新答案。不能发现后缀自动机可以比较轻松的求出一个字串的出现次数，但是需要快速回答。所以需要快速找到一个字串在后缀自动机上的所属节点。

注意到后缀链接连接着一段后缀相等的位置，所以预处理 \([1,i]\) 在后缀自动机的位置，对于一个串 \([s,t]\) ，从 \([1,t]\) 的位置开始跳后缀链接，找到属于 \([s,t]\) 的位置，这里使用倍增跳跃就可以做到一个 \(\log\) 。

有一个细节，空间开不下的话，后缀数组的 \(ch\) 用完了之后可以拿来跳倍增。

代码

#include
    
     #define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)template
     
      inline bool chk_min(T &x,const _T y){return y
      
       
        inline bool chk_max(T &x,const _T y){return x
        
         struct Linked_list{    int head[maxn],nxt[maxm],tot;T to[maxm];    Linked_list(){clear();}    T &operator [](const int x){return to[x];}    void clear(){memset(head,-1,sizeof(head)),tot=0;}    void add(int u,T v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}    #define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i])};Linked_list
         
          G;int ch[N][26],slink[N],len[N],sz[N];int *fa[N];int las,tot;char str[N];int idx[N];char mnc[N];int p[N];int n;ll ans;void init(){ las=tot=1; FOR(i,0,25)ch[1][i]=0; len[1]=slink[1]=0;}void extend(char c){ int p=las,cur=++tot; FOR(i,0,25)ch[cur][i]=0; len[cur]=len[p]+1; sz[cur]=1; for(;p&&!ch[p][c-'a'];p=slink[p])ch[p][c-'a']=cur; if(!p)slink[cur]=1; else { int q=ch[p][c-'a']; if(len[p]+1==len[q]) slink[cur]=q; else { int clone=++tot; FOR(i,0,25)ch[clone][i]=ch[q][i]; slink[clone]=slink[q]; len[clone]=len[p]+1; sz[clone]=0; slink[cur]=slink[q]=clone; for(;p&&ch[p][c-'a']==q;p=slink[p])ch[p][c-'a']=clone; } } las=cur;}void dfs(int u){ EOR(i,G,u) { int v=G[i]; dfs(v); sz[u]+=sz[v]; }}void solve(int l,int r){ int p=idx[r]; DOR(i,20,0)if(len[fa[p][i]]>=r-l+1) p=fa[p][i]; chk_max(ans,1ll*sz[p]*(r-l+1));}void Manacher(char *str,int len){ int n=1; mnc[1]='#'; FOR(i,1,len)mnc[++n]=str[i],mnc[++n]='#'; int mr=0,pos; FOR(i,1,n) { if(i<=mr)p[i]=std::min(p[(pos<<1)-i],mr-i+1); else p[i]=1; while(i-p[i]>=1&&i+p[i]<=n&&mnc[i-p[i]]==mnc[i+p[i]]) { p[i]++; if(mnc[i-p[i]+1]=='#')solve((i-p[i]+1+1)>>1,(i+p[i]-1-1)>>1); } if(chk_max(mr,i+p[i]-1))pos=i; }}int main(){ scanf("%s",str+1); n=strlen(str+1); init(); FOR(i,1,n)extend(str[i]),idx[i]=las; FOR(i,2,tot)G.add(slink[i],i); FOR(i,0,tot)fa[i]=ch[i]; FOR(i,1,tot)fa[i][0]=slink[i]; FOR(j,1,20)FOR(i,1,tot)fa[i][j]=fa[fa[i][j-1]][j-1]; dfs(1); Manacher(str,n); printf("%lld\n",ans); return 0;}