回文树（EER Tree,Palindromic Tree）亦称回文自动机，用于存储一个串中的所有回文子串。
由于回文串可能有奇有偶，于是分为两棵树进行构建，偶跟编号为0，长度为0，fail指向奇根，奇根编号为1，长度为-1，fail指向自身。
fail指向的是该节点的最长回文后缀，新加入字符时跳fail直到其表示的回文串两侧都能添加该字符。
struct PalindromicAutomation{
struct tree{
int ch[26],fail,len,sz/*回文串后缀本质不同的回文串个数*/,cnt/*该回文串出现次数*/,trans/*长度小于自身一半的最长回文后缀*/;
}t[N];
int tot=1,last/*上一次插入字符的编号*/;
#define ch(p,x) (t[p].ch[x])
#define f(p) (t[p].fail)
#define l(p) (t[p].len)
#define s(p) (t[p].sz)
#define c(p) (t[p].cnt)
#define t(p) (t[p].trans)
inline PalindromeAutamation(){
f(0)=f(1)=tot=1;/*偶跟0指向奇根1，奇根指向自身*/
l(1)=-1;/*奇根长度-1，插入第一个字符时+2变成1*/
}
inline int getfail(int x,int n){/*依次跳x的fail直到回文后缀的两端都可以添加s[n]*/
while(n-l(x)-1<0||s[n]!=s[n-l(x)-1])x=f(x);/*左端点不合法或当前回文串两端无法拼接该字符时跳fail*/
return x;
}
inline int gettrans(int x,int n){
while((l(x)+2<<1)>l(tot)||s[n]!=s[n-l(x)-1])x=f(x);/*注意比较的长度是扩展后会加2的长度*/
return x;
}
inline void insert(int x,int c){
int p=getfail(last,x);/*找到上一个位置的最长回文后缀*/
if(!ch(p,c)){
f(++tot)=ch(getfail(f(p),x),c);/*更新新建节点的fail指针*/
l(tot)=l(p)+2;/*长度比父亲长度大2*/
ch(p,c)=tot;/*更新儿子*/
s(tot)=s(f(tot))+1;/*本质不同回文串个数，即状态数*/
if(l(tot)<=2)t(tot)=f(tot);/*自身长度小于2则trans就是自己的fail*/
else t(tot)=ch(gettrans(t(p),x),c);/*否则跳trans*/
}
last=ch(p,c);/*上一个点插入后的编号*/
c(last)++;/*出现次数*/
}
inline void makecount(){/*统计每个回文串出现的次数*/
for(int i=tot;i;i--)c(f(i))+=c(i);/*倒序累加后缀和，因为一个回文串的fail即为其回文后缀，一定至少出现了和自己一样的次数*/
}
inline void clear(){
for(int i=0;i<=tot;i++)for(int j=0;j<4;j++)ch(i,j)=0;
f(0)=f(1)=tot=1;
l(1)=-1;
last=0;
}
}pa;
双倍回文串，一个字符串是双倍回文串当且仅当它可以分为两个长度相同且均为2的倍数的回文串，求一个字符串的最长双倍回文串的长度。维护trans指针，一个字符串满足要求当且仅当其trans长度是自身的一半且为2的倍数。
inline int db(){
int re=0;
for(int i=1;i<=tot;i++)if((l(t(i))<<1)==l(i)&&(l(t(i))&1)==0)re=max(re,l(i));
return re;
}
用两种操作构造出给定字符串，在字符串开头或末尾添加一个任意字符，或在开头或末尾添加一个该串的逆串，求最小步数。最终答案肯定由一个回文串和一些剩余部分组成，设f[i]表示形成回文树上i点表示的回文的最小步数，若由边x->y，则可在形成x前加一个字符后再形成y，则f[u]=f[x]+1，同时维护每个点的trans表示小于当前点长度一半的最长回文后缀，从trans[i]暴力拼接到len[i]/2，再一步拼接到i.
inline int solve(){
int ans=n;
queue<int>q;
for(int i=2;i<=tot;i++)f[i]=l(i);
for(int i=0;i<=3;i++)if(ch(0,i))q.push(ch(0,i));
while(!q.empty()){
int x=q.front();
q.pop();
f[x]=min(f[x],f[t(x)]+1+(l(x)>>1)-l(t(x)));
ans=min(ans,n-l(x)+f[x]);
for(int i=0;i<=3;i++){
if(!ch(x,i))continue;
int y=ch(x,i);
f[y]=min(f[y],f[x]+1);
q.push(y);
}
}
return ans;
}
求两个字符串的最长公共回文子串。为两个串构建回文树，中间不要清空，分别标记走过的节点，若有一个点都被标记过，那么用它代表的回文串来更新答案。
inline void solve(){
int ma=0,cnt=0;
for(int i=2;i<=tot;i++){
if(flag[i][0]&&flag[i][1]){
if(ma<l(i))ma=l(i),cnt=1;
else if(ma==l(i))cnt++;
}
}
cout<<ma<<' '<<cnt<<'\n';
}
求两个串的公共回文串对数。两个串插入一棵回文树，中间不要清空，标记走过的节点，乘法原理计算答案。
inline void makecount(){/*统计每个回文串出现的次数*/
for(int i=tot;i;i--)c(f(i))+=c(i);/*倒序累加后缀和，因为一个回文串的fail即为其回文后缀，一定至少出现了和自己一样的次数*/
for(int i=tot;i;i--)flag[f(i)][0]+=flag[i][0],flag[f(i)][1]+=flag[i][1];
int cnt=0;
for(int i=2;i<=tot;i++)cnt+=flag[i][0]*flag[i][1];
cout<<cnt;
}
求一个字符串每个长度有多少个特殊回文串，特殊回文串为自己是回文串且它的前一半也是回文串。考虑fail指针的含义，指向该节点的最长回文后缀，那么对fail指针建树的话，路径上的点就都是子节点的前缀，对于一个点只要自己长度一半也存在，那么这个点代表的回文串就是合法的。
struct PalindromicAutomation{
struct tree{
int ch[26],fail,len,sz,cnt;
inline tree(int fail=0,int len=0,int sz=0,int cnt=0):fail(fail),len(len),sz(sz),cnt(cnt){
memset(ch,0,sizeof(ch));
}
};
int last;
vector<tree>t;
string s;
#define ch(p,x) (t[p].ch[x])
#define f(p) (t[p].fail)
#define l(p) (t[p].len)
#define s(p) (t[p].sz)
#define c(p) (t[p].cnt)
inline int getfail(int x){
int n=s.size()-1;
while(s[n-l(x)-1]!=s[n])x=f(x);
return x;
}
inline PalindromicAutomation(){
t.push_back(tree(1,0));
t.push_back(tree(1,-1));
s="~";
}
inline void clear(){
last=0;
t.clear();
t.push_back(tree(1,0));
t.push_back(tree(1,-1));
s='~';
}
inline void insert(char c){
s+=c;
c-='a';
int p=getfail(last);
if(!ch(p,c)){
t.push_back(tree(ch(getfail(f(p)),c),l(p)+2,s(p)+1));
ch(p,c)=t.size()-1;
}
last=ch(p,c);
c(last)++;
}
inline void makecount(){
for(int i=t.size()-1;i;i--)c(f(i))+=c(i);
}
void dfs(int x,vector<int>&ans,vector<vector<int>>&e,vector<int>&len,vector<int>&ok){
if(l(x)!=-1)len[l(x)]=1;
if(len[l(x)+1>>1])ok[x]=1;
for(int y:e[x])dfs(y,ans,e,len,ok);
if(l(x)!=-1)len[l(x)]=0;
}
inline void getans(int n){
vector<int>ans(n+1,0),len(n+1,0),ok(t.size(),0);
vector<vector<int>>e(t.size());
for(int i=0;i<t.size();i++)e[f(i)].push_back(i);
dfs(0,ans,e,len,ok);
makecount();
for(int i=t.size()-1;~i;i--)if(ok[i])ans[l(i)]+=c(i);
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<'\n';
}
}pa;