2017/8/3更新
这篇东西是很久之前写的了，最近重新整理了一个ppt在3.47里面；WWT的集训队论文写得也够好了。
前言
这个东西呢，是由战斗民族的信息选手Mikhail Rubinchik搞出来的一个数据结构，正如其名，就是用来解决回文相关的题目的。应该说，是manacher的一个特殊化，所以他跟manacher有很多相似之处。
整体感知
这是由两棵树组成的东西，一棵树存长度为奇数的回文串-tr1，另一个存偶数的-tr2，而每个节点表示一个回文串，其中两树根节点表示的回文串长度分别为0,1。建树的过程，就是每次在加入串-P后面放多一个字符，（这个加入串P就是原串的一个前缀），然后找出最长回文后缀-T，如果树中没有相同的节点就新建，有的话就给这个点的cnt +1，表示又有一个加入串的 最长 回文后缀是这个（最长不能漏）。
新建节点后，设T=’x’+回文串S1+’x’，则表示T的节点为表示S1节点的子节点。
为了时间复杂度尽量小，也就是这个数据结构的精华——后缀链，这个时候也要更新。
后缀链：除了两棵树的根节点，一个节点x的后缀链所连向的节点y，是x表示的回文串的最长回文后缀或者前缀（不能是他本身）。有什么用等下再说。
给个图会清晰点
文章图片
细细构造结构
设原串为S
1，每次对于一个加入串P，他长度为i，我们要快速找出回文后缀，这个时候我们用前面的信息，就可以快速弄出。
【回文树/回文自动机|回文树/回文自动机 Palindromic Tree 学习小记】2，假设之前的加入串为P’，P比他多一个’x’，之前P’的最长回文后缀是T。
3，那么这个时候，我们就要找出一个P’的回文后缀Key，使得Key的前一个字符为’x’。即S[i]=S[i-length(Key)-1]=’x’（这个时候大家应该发现长度为-1有什么用了）。
4，我们从T开始找，明显的，如果T不是，我们就沿着表示T的节点的后缀链走。好，走到了一个表示T1的节点，其中T1是T的最长回文后缀，假如还不是，就一直往后找，直到找到，无论怎样，这个找到-1的一定是了。
如图 
文章图片
唔，好了，我们找到了，然后就像整体感知所讲的做咯。
分析
在分析时间空间复杂度之前，要说明一点:
长度为n的字符串x，怎样也只有n个本质不同的回文串。
如果不懂的话先去学manacher吧，学完会知道，因为manacher也用了这一点，而且manacher好学。
时间复杂度：
构建点是O(n)的，而找对于最长回文后缀的时间：由于我们沿后缀链跳的时候，回文中心是不断往后走的，所以最多O(2n)，如此一来，时间复杂度是线性的。
空间复杂度：
点只有n个~~~
不用说了吧···
应用
自己想想吧，反正那个cnt并不是表示原串中这个回文串有多少个，如果要用这个，就要沿着后缀链（fail数组）从后往前加。
其实这个东西应用的地方比较少，因为跟manacher有很多重叠。
因为是战斗的民族发明的东西，所以简单粗暴，只是把一些题变成裸题。
代码
#include
#include
#include
#include
using namespace std;
#define fo(i,j,k) for(i=j;
i<=k;
i++)
#define fd(i,j,k) for(i=j;
i>=k;
i--)
#define ll long long
const int N=300005;
ll i,dur,t,ans,now,ds,n,len[N],b[N][26],fail[N],cnt[N];
char s[N];
ll get(ll x)
{
while (s[i]!=s[i-len[x]-1])
x=fail[x];
return x;
}
ll ins()
{
now=get(dur);
ds=s[i]-'a';
if (b[now][ds]==0)
{
fail[++t]=b[get(fail[now])][ds];
len[t]=len[now]+2;
b[now][ds]=t;
}
cnt[b[now][ds]]++;
dur=b[now][ds];
}int main()
{
scanf("%s\n",s+1);
n=strlen(s+1);
len[0]=0;
len[1]=-1;
t=1;
fail[1]=1;
fail[0]=1;
dur=0;
fo(i,1,n)
ins();
//之后就是一个应用，前面都是构造
ans=0;
fd(i,t,0)
{
ans=max(ans,len[i]*cnt[i]);
cnt[fail[i]]+=cnt[i];
//这个就是应用提到的累加
}
printf("%lld\n",ans);
} 参考文献
1，好友Crazy的学习小记
2，Victor Wonder 《回文树的构建及其应用》
3，Chunkit佬的漂亮代码
注明：图都来自2的论文，懒得画了，非常感谢论文对我的帮助
