回文树/回文自动机/PAM总结——题解 P3649 【[APIO2014]回文串】

### 【题目】  ### 【分析】 - 回文树裸题。 ### 【算法简介】 - 回文树，又称回文自动机，简称PAM。 - 作用：线性的时间复杂度求一个字符串里的回文串的个数，也可以通过记录多一些信息来实现更多的功能。 ### 【算法步骤】 - 顾名思义，“回文自动机”与[AC自动机](https://12349.blog.luogu.org/ac-zi-dong-ji-zong-jie)有非常多的联系： - 同样使用失配指针节约时间； - 同样使用Trie树结构。 - 定义：len[i]表示第i个结点的回文串长度，fail[i]表示第i个结点的失配指针，son[i][c]表示结点i的字符c边指向的结点。 - PAM的有2个根，一个根代表偶长度的回文串（以下称为偶根），另一个代表奇长度的回文串（以下称为奇根）。特别的，定义偶根长度为0，fail指向自己，奇根的长度为-1（这里十分玄妙），fail指向自己。 - 与AC自动机相似，枚举字符串的每一位，求出最早到达的加上自己这一位后成为回文串的结点，如果不行就跑向失配指针，然后把插入回文自动机（如图）： - 自己作为找到的结点的儿子c。 - len是上一次的len+2； - fail是找到的结点的fail的儿子。 - 累计数量。  - 最终的答案就是所有结点的累计数量*长度的MAX。 ### 【拓展】 - 累计数量的步骤可以像AC自动机一样，改为或添加各种玄妙的操作。 ### 【参考程序】 ```cpp #include<cstdio> #include<cstring> #include<iostream> using namespace std; typedef long long LL; #define int LL struct PAM{ int len,fail,son[30]; }Ptree[300005]; int tot,last,len,l; int cnt[300005]; char st[300005]; void Init() { Ptree[0].len=0; Ptree[1].len=-1; Ptree[0].fail=1; tot=1; last=0; } int Get(int now) { for (;st[l]!=st[l-Ptree[now].len-1];now=Ptree[now].fail); return now; } void Add(int ch) { int u=Get(last); if (Ptree[u].son[ch]==0) { int v=++tot; Ptree[v].len=Ptree[u].len+2; Ptree[v].fail=Ptree[Get(Ptree[u].fail)].son[ch]; Ptree[u].son[ch]=tot; } last=Ptree[u].son[ch]; cnt[last]++; } signed main() { scanf("%s",st+1); len=strlen(st+1); Init(); for (l=1;l<=len;l++) Add(st[l]-'a'); int ans=0; for (int i=tot;i>1;i--) { cnt[Ptree[i].fail]+=cnt[i]; ans=max(ans,cnt[i]*Ptree[i].len); } cout<<ans; return 0; } ```