)
回文自动机一般用于解决字符串中的回文问题，当马拉车无法很好的解决问题时，自由度更高的回文自动机便成为了首选。
回文自动机跟 AC 自动机有点相似，它同样要建立出一个“回文树”，我们来具体介绍一下这个“回文树”：
回文串分奇偶两种，因此，我们把 PAM 的状态分成两个部分，一部分存奇回文串，另一部分存偶回文串。
同理，我们把根也分为奇根（图中的点 1）和偶根（图中的点 0）。它们不表示任何字符串，只作为初始状态而存在。
树上除了根以外的任意一个点都代表一个回文串，我们从这个点一直读到根，再读回到这个点，即为其代表的回文串。
特别的，如果是奇回文串，则与根相连的那个字符边只读一次。
如图，\(s="abcabc"\) 建出的 PAM 如下图：
我们举几个例子：
点 4 代表的回文串是 \(aba\)。点 7 代表的回文串是 \(c\)。点 6 代表的回文串是 \(baab\)。
当然，这个树上也有 fail 指针，我们参考下图理解：
这个是 \(abbaabba\) 的回文树。
我们举个例：
点 8 代表的串是 \(bbaabb\)，当它失配时，我们跳到点 4，也就是 \(bb\)。
如果此时我们加入的字符是 \(a\)，发现可以组成 \(abba\) 这一个回文串，我们就配对即可。
因此我们发现，我们 getfail 的条件就是 s[i-lenB[x]-1]!=s[i]，满足这个时我们就可以不用继续往 fail 跳了，当然有可能出现 i-lenB[x]-1<=0 的情况，这种情况下我们还要继续跳。
我们引入一个性质：一个串的本质不同的回文子串最多有 \(n\) 个，也就可以推出我们加入一个点时最多只会产生一个新的回文串。
然后就是和 AC 自动机一样的操作，不存在就建立点，存在就直接走。
那我们剩下的唯一一个问题就是，在新建点时要怎么操作？
我们先考虑这个点的 fail 应该连向哪里，我们肯定得在 fail[pos] 找，然后我们发现为了满足添加了这一个字母以后其依然是一个回文串，所以所要的点必然是 getfail(fail[pos],i)，那我们直接 fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'] 就可以了。
在初始化中 fail[0]=1,fail[1]=0,len[1]=-1 即可。
统计长度，我们直接 len[tot]=len[pos]+2。统计数量，我们 sum[now]++，最后 sum[fail[i]]+=sum[i] (i:2~tot) 即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
string s;
ll siz,fail[2000005],len[2000005],ans,tot=1,sum[2000005];
ll tr[2000005][26];
ll getfail(ll x,ll i){while(i-len[x]-1<0||s[i-len[x]-1]!=s[i]){x=fail[x];}return x;
}
int main(){cin>>s;siz=s.size();fail[1]=0;fail[0]=1;len[0]=0;len[1]=-1;ll now=0;for(int i=0;i<siz;i++){ll mb=getfail(now,i);if(!tr[mb][s[i]-'a']){fail[++tot]=tr[getfail(fail[mb],i)][s[i]-'a'];tr[mb][s[i]-'a']=tot;len[tot]=len[mb]+2;sum[tot]=sum[fail[tot]]+1;}now=tr[mb][s[i]-'a'];}
}