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;
}
上一篇: jung 实例代码(原创)
下一篇: 为什么说Java中只有值传递