欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAM-回文自动机-模板

程序员文章站 2024-03-09 08:15:29
...

个人理解

回文自动机顾名思义,是解决回文串相关问题的。其又称回文树。树上的每个节点对应串中的一个回文串。树根有两个,分别为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;
}