回文自动机

写一篇文章来详解一下回文自动机吧，之前没弄懂吃了大亏。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5;
const int sigma_size = 26;

struct Palindromic_Tree{
    int ch[maxn][sigma_size];//next数组
    int f[maxn];//表示失配指针，具体来说就是与当前点有相同后缀（最长）最近的位置
    int cnt[maxn];//表示当前节点前的那一个回文串在整个数组中总共出现了几次（调用count后）
    int num[maxn];//以当前节点结尾的回文串的种类数
    int len[maxn];//以当前节点为结尾的回文串的最长长度
    int s[maxn];//储存字符
    int last;
    int n;
    int p;

    int newnode(int w){
        for(int i=0;i<sigma_size;i++)ch[p][i] = 0;
        cnt[p] = 0;
        num[p] = 0;
        len[p] = w;
        return p++;
    }

    void init(){
        p = 0;
        newnode(0);
        newnode(-1);
        last = 0;
        n = 0;
        s[n] = -1;
        f[0] = 1;        
    }

    int getfail(int x){
        while(s[n-len[x]-1]!=s[n])x = f[x];//向前找相同后缀的并比较后一位是否相等，相等则返回（因为寻找的默认是最长优先，所以保证找到的回文串一定是最长的）
        return x;
    }
    
    void add(int c){
        c-='a';
        s[++n] = c;
        int cur = getfail(last);
        if(!ch[cur][c]){
            int now = newnode(len[cur]+2);
            f[now] = ch[getfail(f[cur])][c];
            ch[cur][c] = now;
            num[now] = num[f[now]] + 1;
        }
        last = ch[cur][c];
        cnt[last]++;
    }

    void count(){
        for(int i=p-1;i>=0;i--){
            cnt[f[i]]+=cnt[i];//统计每个节点对应的某种回文串出现的次数
        }
    }
}solver;

char str[maxn];
int main(){
    solver.init();
    scanf("%s",str);
    int len = strlen(str);
    long long ans = 0;
    for(int i=0;i<len;i++)solver.add(str[i]);
    solver.count();
    for(int i=2;i<solver.p;i++){//0表示偶数树上的节点，1表示奇数树上的节点，所以要从2开始遍历
        ans = max(ans,1LL*solver.len[i]*solver.cnt[i]);
    }
    printf("%lld\n",ans);
    return 0;
}