回文树

具体思想不多说
struct node{
int son[26];
int len;
int fail;
}t[N];

int cnt = 1,last = 0;
void init(){
t[0].fail = 1;
t[1].len = -1;
}
int getfail(int p,int r){
while(r-t[p].len-1 < 0 || s[r-t[p].len-1] != s[r])
p = t[p].fail;
return p;
}
int insert(int x,int r){
int father = getfail(last,r);
int now = t[father].son[x];
if(!now){
now = ++cnt;
t[now].len = t[father].len + 2;
t[now].fail = t[getfail(t[father].fail,r)].son[x];
t[father].son[x] = now;
}
last = now;
}
在此解释一下我开始搞不懂的地方
首先是t[now].fail = t[getfail(t[father].fail,r)].son[x];
T是S[i-1]所处理出的最长回文串，我们现在处理S[i],S[i]的字符为X，首先在T中一直找，它会找出A这个回文串，前面正好是X，当然A也可能是空串，现在这个点就是father结点，我们把X连到它的儿子上

那么X所在t中的结点代表的回文串就是XAX
现在要处理X在t中结点的fail指针，我们要找的是最长公共后缀，此时就不能包括father结点所代表的回文串了，只能从father结点沿着fail往上找，因为也就是在A里面找出XB，B为回文串

假如能找出XB，那么XBX一定是处理过了的，所以B在t中的结点一定有son[x]