PAM-回文自动机-模板

个人理解

回文自动机顾名思义，是解决回文串相关问题的。其又称回文树。树上的每个节点对应串中的一个回文串。树根有两个，分别为0和1。0是所有偶回文的树根，1是所有奇回文的树根。在树上父子之间长度差2。类似ac自动机，回文自动机也有相应的fail指针。其指向当前编号的最长回文后缀。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 5e5 + 5;
struct PAM_node//回文树上节点
{
    int vis[26];
    int fail, len, num;
};
struct PAM//回文树/回文自动机
{
    PAM_node pn[N];
    int n, length, last, cnt, s[N];
    char str[N];
    PAM()//初始化
    {
        pn[0].len = 0;//0号点是偶回文的根节点
        pn[1].len = -1;//1号点是奇回文的根节点
        pn[0].fail = 1;
        pn[1].fail = 0;
        last = 0;
        cnt = 1;//插入节点从二号开始
    }
    void read()//读入字符串
    {
        cin >> (str + 1);
        length = strlen(str + 1);
    }
    int get_fail(int x)//获取当前位置的最长回文后缀（回文树的fail指针）
    {
        while(s[n - pn[x].len - 1] != s[n])//pn[x].len 存的是编号为x的回文串长度
            x = pn[x].fail;
        return x;
    }
    void insert()
    {
        int p = get_fail(last);
        if(!pn[p].vis[s[n]])//没有子节点
        {
            pn[++ cnt].len = pn[p].len + 2;//每次添加两个字符
            int tmp = get_fail(pn[p].fail);
            pn[cnt].fail = pn[tmp].vis[s[n]];
            pn[cnt].num = pn[pn[cnt].fail].num + 1;
            pn[p].vis[s[n]] = cnt;
        }
        last = pn[p].vis[s[n]];
    }
    void solve()
    {
        int k = 0;
        s[0] = 26;
        for(n = 1; n <= length; n ++)
        {
            str[n] = (str[n] - 97 + k) % 26 + 97;
            s[n] = str[n] - 'a';
            insert();
            cout << pn[last].num << " ";
            k = pn[last].num;
        }
    }
}pam;
int main()
{
    ios::sync_with_stdio(false);
    pam.read();
    pam.solve();
    return 0;
}