回文自动机

回文自动机，PAM(Palindrome Auto Machine)，也叫回文树，是一位战斗民族的算法专家Mikhail Rubinchik在2015年发明的专门用于回文研究的数据结构。

PAM的功能很强大(讲真)。它有点像AC自动机，当然也是一个自动机，树形上也是采用的Trie树结构，只是表达的意义和标准Trie树、AC自动机里的Trie树不一样罢了，在后两者中，Trie树上的边存储着字符信息，从根节点到任意节点表达的是一个字符串，即沿着某条边向下走，当前字符串的后面就新加一位该边上存储的字符。而在PAM中，沿着某条边向下走，当前字符串的两边都要加上该边存储的字符，即从根节点到任意节点表达的是一个回文字符串。这个是要知道的，大概的PAM就长这样。
回文字符串有两种：长度为奇数和长度为偶数的回文串。这两个的区别也很明显，所以在PAM上有两个根，分别来存储两种形式上不同的回文字符串。这两个根是0根和1根(Trie只有0根)。0根存储长度为偶数的回文串，1存储长度为奇数的回文串。
类似于AC自动机，PAM也有fail边，某个结点a的fail边指向的结点b所表达的回文串，是结点a的最长的回文串后缀(如回文串ababa，它有两个回文串后缀aba和a，aba是最长的)。特殊的，0根的fail边指向1根，1根也指向1根(其实1的fail边无所谓，不同的板子可能会不一样)。
字符串ababaa在PAM中的形状如下：

接下来讲如何构造PAM

不同于AC自动机，PAM的fail边是在线构造的，即每插入一个新的字符，就连上这个新结点的fail边。(AC自动机是把所有字符串都插入后才开始连fail边，且不能修改)
声明几个用到的变量：

Trie[][27]：用来存储所有信息的树结构
size：Trie中已经用了的结点个数。
mp[i]：字符串中下标为i的字符对应于Trie树中哪一个结点
fail[j]：fail边，j结点所表示的回文串的最大回文后缀(fail[j]结点所表示的回文串)
Root0：0根
Root1：1根
last：最新插入的结点的位置
Len[j]：结点j对应的回文字符串的长度
cnt[j]：结点j对应的回文字符串中，不同的回文串后缀的个数。
Half[i]：Half[i]表示结点i的长度不超过Len[i]/2的最大回文后缀

最后1个是根据实际需要时要设立的一些变量，前面的变量是PAM所必需的。因此先讲前面的几个变量如何构造与赋值。
Len[i] = Len[last] + 2
Cnt[i] = Cnt[fail[i]] + 1
half指针要在i的父亲结点的half指针的fail链里面寻找。
当Len[i]<=2时，half=fail。
需要实时更新的变量有last，mp[i]你得映射好，fail边得连上，cnt得弄好，还有half。

板子

typedef struct PAM{
    int size,last,root0,root1,Trie[maxn][27],fail[maxn];
    int Len[maxn],mp[maxn],cnt[maxn];
    PAM(){
        size = 2;
        root0 = 0, root1 = 1, last = root1;
        Len[root0] = 0, fail[root0] = root1;
        Len[root1] = -1, fail[root1] = root1;
    }
    void Extend(char ch,int idx){
        while (str[idx-1-Len[last]]!=str[idx]) last = fail[last];
        if (!Trie[last][ch-'a'+1]){
            int v = fail[last];
            while (str[idx-1-Len[v]]!=str[idx]) v = fail[v];
            //这里这个地方很重要，先连fail边，再给Trie上添加新的点，为防止fail指向自己！！
            size++;
            fail[size] = Trie[v][ch-'a'+1];
            Trie[last][ch-'a'+1] = size;
            //
            Len[size] = Len[last] + 2;
            cnt[size] = cnt[fail[size]] + 1;
            //
            if (Len[size]<=2)   trans[size] = fail[size];
            else{
                int tp = trans[last];
                while (s[idx-Len[tp]-1]!=s[idx] || Len[tp]+2>Len[size]/2) tp = fail[tp];
                trans[size] = Trie[tp][ch-'a'+1];
            }
        }
        mp[idx] = Trie[last][ch-'a'+1];
        last = Trie[last][ch-'a'+1];
    }
    void Build(char *str){
        int len = strlen(str+1);
        for (int i=1;i<=len;i++)
            Extend(str[i],i);
    }
}PAM;

应用

1.求一个字符串中本质不同的回文串的个数。
我们知道在Tire树中不会有两个字符串重复的，所以在PAM里的Trie中，除了0根和1根外，剩下的结点都唯一表示一个回文串，即本质不同的回文串有size-1个。
2.统计每个回文串出现的次数。洛谷P3649 回文串
跑一遍fail树，类似于AC自动机了。需要用到拓扑排序

例题
洛谷P3649 回文串
构造PAM，回文自动机，然后对fail树拓扑排序，最后输出答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+50;
char str[maxn];
typedef struct PAM{
    int size,last,root0,root1,Trie[maxn][27],fail[maxn];
    int Len[maxn],mp[maxn],cnt[maxn],times[maxn],in[maxn];
    PAM(){
        size = 1;
        root0 = 0, root1 = 1, last = root1;
        Len[root0] = 0, fail[root0] = root1;
        Len[root1] = -1, fail[root1] = root1;
    }
    void Extend(char ch,int idx){
        while (str[idx-1-Len[last]]!=str[idx]) last = fail[last];
        if (!Trie[last][ch-'a'+1]){
            int v = fail[last];
            while (str[idx-1-Len[v]]!=str[idx]) v = fail[v];
            fail[++size] = Trie[v][ch-'a'+1];               //必须要先连fail边
            Trie[last][ch-'a'+1] = size;
            Len[size] = Len[last] + 2;
            cnt[size] = cnt[fail[size]] + 1;
            in[fail[size]]++;
        }
        mp[idx] = Trie[last][ch-'a'+1];
        last = Trie[last][ch-'a'+1];
        times[mp[idx]]++;
    }
    void Build(char *str,int len){
        for (int i=1;i<=len;i++)
            Extend(str[i],i);
        topu();
        return;
    }
    void topu(){
        queue<int> q;
        for (int i=2;i<=size;i++)   if (in[i]==0)
            q.push(i);
        while (!q.empty()){
            int temp = q.front();   q.pop();
            times[fail[temp]] += times[temp];
            in[fail[temp]]--;
            if (in[fail[temp]]==0)
                q.push(fail[temp]);
        }
        return;
    }
}PAM;
PAM P;
int main(){
    //freopen("P3649_8.txt","r",stdin);
    ll len,ans;
    scanf ("%s",str+1);
    len = strlen(str+1);    ans = 0;
    P.Build(str,(int)len);
    for (int i=2;i<=P.size;i++)
        ans = max(ans,(ll)P.times[i] * P.Len[i]);
    printf ("%lld",ans);
    return 0;
}

洛谷 P4287 双倍回文

把0根里的，长度为4的倍数的回文串和它的half回文比较，判断后者是否是前者的一半即可。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
const int maxn = 5e5+5;
int len;
char s[maxn];
typedef struct PAM{
    int Trie[maxn][27],fail[maxn],size,Len[maxn],last;
    int ans,half[maxn];
    PAM(){
        fail[0] = fail[1] = 1;
        Len[0] = 0,Len[1] = -1;
        size = 1;   last = 1;
        ans = 0;
    }
    void Insert(char ch,int idx){
        while (s[idx-1-Len[last]]!=s[idx])  last = fail[last];
        if (!Trie[last][ch-'a'+1]){
            int v = fail[last];
            while (s[idx-Len[v]-1]!=s[idx]) v = fail[v];
            fail[++size] = Trie[v][ch-'a'+1];
            Trie[last][ch-'a'+1] = size;
            Len[size] = Len[last] + 2;
            //
            if (Len[size]<=2)   half[size] = fail[size];
            else{
                int tp = half[last];
                while (s[idx-Len[tp]-1]!=s[idx] || Len[tp]+2>Len[size]/2) tp = fail[tp];
                half[size] = Trie[tp][ch-'a'+1];
            }
        }
        last = Trie[last][ch-'a'+1];
    }
    void Build(char *s,int len){
        for (int i=1;i<=len;i++){
            Insert(s[i],i);
        }
        queue<int> q;
        for (int i=1;i<=26;i++) if (Trie[0][i])
            q.push(Trie[0][i]);
        while (!q.empty()){
            int tp = q.front(); q.pop();
            if (Len[tp]%4==0 && Len[half[tp]]==Len[tp]/2) ans = max(ans,Len[tp]);
            for (int i=1;i<=26;i++) if (Trie[tp][i])
                q.push(Trie[tp][i]);
        }
        return;
    }
}PAM;
PAM P;
int main(){
    scanf ("%d %s",&len,s+1);
    P.Build(s,len);
    printf ("%d\n",P.ans);
    return 0;
}