先膜一下nblt，是nblt教了我会问自动机

下面进入正文。

回文自动机，顾名思义，处理回文串的自动机

为了方便，自动机中只有回文串的下半段

考虑manacher

每当变量mx＋1时，就在自动机中加点（也可能已经有那个点，这时只要标记一下这个点所在的位置）

然后考虑加在哪里

找出这个回文串的最早出处（新建一个数组暴力往前跳，这里有个优化，如果不加会T2333）

然后在这个回文串的对应位置继续加点

然后考虑fail的建立

因为是回文

所以fail还有个条件

就是必须是回文

所以在建fail的时候需要多判一个条件，其他没了~

下面是bzoj3676的板子

#include<cstdio>
#include<cstring>
using namespace std;
int n,i,get[600010],tmp,kt,f[600010],wz[600010],j,cs[600010],t;
int son[600010][30],cur,pre[600010],tot[600010];
long long ans;
char s[600010];
int find(int x,int y)
{
    if(get[x]<y)return wz[x+y];
    for(;get[pre[x]]>=get[x];pre[x]=pre[pre[x]]);return find(pre[x],y);
}
void ddfs(int x)
{
    for(int i=0;i<27;i++)
        if(son[x][i])ddfs(son[x][i]),tot[x]+=tot[son[x][i]];
}
int main()
{
    scanf("%s",s+1);n=strlen(s+1);get[0]=-1;
    for(i=n;i>=1;i--)s[i<<1]=s[i]-'a',s[i<<1|1]=26;
    s[0]=27;s[1]=26;n<<=1;n++;kt=0;tmp=0;s[n+1]=28;
    for(i=1;i<=n;i++)
    {
        if(i>tmp)
        {
            for(tmp=i,cur=0;s[tmp]==s[i*2-tmp];cur=son[cur][s[tmp]],wz[tmp++]=cur)
                if(!son[cur][s[tmp]])son[cur][s[tmp]]=tmp;
            tmp--;kt=i;f[i]=tmp-i;get[i]=-1;
        }else
        {
            f[i]=f[kt*2-i];pre[i]=kt*2-i;get[i]=f[i];
            if(f[i]+i>=tmp)
            {
                get[i]=tmp-i;
                for(cur=find(i,tmp-i),tmp++;s[tmp]==s[i*2-tmp];cur=son[cur][s[tmp]],wz[tmp++]=cur)
                    if(!son[cur][s[tmp]])son[cur][s[tmp]]=tmp;
                tmp--;kt=i;f[i]=tmp-i;
            }
        }tot[find(i,f[i])]++;
    }for(i=0;i<=n;i++)
        for(j=0;j<27;j++)
            if(son[i][j])cs[son[i][j]]=cs[i]+1;ddfs(0);
    for(i=1;i<=n;i++)if(1ll*(cs[i]-1)*tot[i]>ans)ans=1ll*(cs[i]-1)*tot[i];
    printf("%lld\n",ans);
}

因为本题不需要用到fail指针所以没有建

刚刚所说的优化就是类似并查集的路径压缩~

感觉还是要加的，不加这题就会T

（或许可以被卡掉？）