http://acm.timus.ru/problem.aspx?space=1&num=1960
题意：给一个串s，要求输出所有的s[0]~s[i]，i<|s|的回文串数目。（|s|<=10^5）
#include <bits/stdc++.h>
using namespace std;
struct PT {
static const int nS=26, nL=100015, N=nL;
int f[N], l[N], c[N][nS], id[N], s[nL], cnt[N], num[N], tot, n, all, dif, last;
int newnode(int _l=0) { l[tot]=_l; return tot++; }
PT() { newnode(); newnode(-1); f[0]=1; n=0; all=0; dif=0; last=0; s[0]=-1; }
inline int getf(int x) { while(s[n]!=s[n-l[x]-1]) x=f[x]; return x; }
void add(int x) {
s[++n]=x;
int q=getf(last);
if(!c[q][x]) {
int now=c[q][x]; now=newnode(l[q]+2);
f[now]=c[getf(f[q])][x];
c[q][x]=now;
num[now]=num[f[now]]+1;
}
last=id[n]=c[q][x];
x=c[q][x];
if(!cnt[x]) ++dif;
++cnt[x];
}
int getdif() { return dif; }
}t;
char s[100015];
int main() {
scanf("%s", s);
for(int i=0, n=strlen(s); i<n; ++i) t.add(s[i]-'a'), printf("%d ", t.getdif());
return 0;
}
回文树（回文自动机）系列= =跪跪跪orz
教程请移步：http://blog.csdn.net/u013368721/article/details/42100363
大概来说说？
（回文后缀：从回文串的中点开始的到串末的字符串，奇数串的回文后缀包括中间点
（回文串的后缀：回文串的后缀
定义节点$A$，转移的状态是$T(A, c)$（从$A$转移到字符为$c$的节点），$A$的失配节点为$F(A)$表示最长的$A$的的后缀的节点，$A$节点代表的回文串长度为$L(A)$，维护的字符串的长度为$Len$，$last$表示当前串的最后一个字符所在的最长的回文后缀的节点（即每次添加字符后的节点）
节点$A$表示的是：从根到$A$所经过的所有$T(B, x)$的$X={x}$，即为原串的回文后缀
考虑在添加一个字符$c$使得原串变为$S+c$。
1、如果$S(Len-L(last)) = c$，那么$last$能转移到$last$所表示的回文串两端加上$c$的回文串。如果不存在转移$T(last, c)$则新建一个节点$B$，$L(B)=L(last)+2$，$F(A)=T(find(F(last)), c)$（这里的$find(a)$表示从$a$一直沿着失配指针走使得能得到一个以$c$结尾的回文串（此刻一定是最长的后缀）。如果没有这个转移，那么这个转移返回$Null$）
2、如果$S(Len-L(last)) eq c$，则沿着$last$的失配指针走直到满足上述情况（否则从根新建转移$T(root, c)$。
可是该如何定义根$root$？如何定义失配指针为$Null$？如何区分奇偶回文串？
答案是两个根，表示指向奇数回文串的根和指向偶数回文串的根。令奇数根表示为$odd$，偶数根表示为$even$，令$F(even) = odd$，$L(even) = 0$，$L(odd) = -1$。（为啥这样做呢？请看下边...
首先来搞情况2的找失配指针的操作，使得如果没有一个失配节点满足存在一个长度大于$1$的回文串的后缀，则长度应该为$1$并由$odd$转移得到。
由于找失配节点时长度节点的长度严格递减，因此我们只需满足失配指针最后走到时$odd$便停止即可。发现$S(Len-L(x)-1)$可以在$x = odd$的情况下满足！那么问题解决= =（即我们在加入一个字符时先$Len = Len+1$
然后来搞情况1的$find$操作。同上面的分析，由于走到$odd$就会停下来，那么在此之前一定要访问过了$even$（因为长度为$2$的回文串比长度为$1$的回文串长= =即因为$S(Len-L(even)-1)=S(Len-1)$，那么这是偶数的回文串应该由$even$转移到），故$null = even$。
（其实好像还要证明当同一个回文串一定转移到同一个节点= =...但是感觉太麻烦？（其实是不会证= =
好像就完了？
有了回文树以后，能支持：
1、询问本质不同的回文串数目
2、询问每种回文串的数目
3、询问所有回文串的数目
4、等等等= =
由定义很容易做出操作1和2和3= =
//由于点的顺序是刚好是拓扑序的，所以我们从后往前就可以更新cnt了。。。（而不用像我这样更新= =是会tle的。。。
放出所有操作的代码：
#include <bits/stdc++.h>
using namespace std;
struct PT {
static const int nS=26, nL=100015, N=nL;
int f[N], l[N], c[N][nS], id[N], s[nL], cnt[N], num[N], tot, n, all, dif, last;
int newnode(int _l=0) { l[tot]=_l; return tot++; }
PT() {
#define C(a) memset(a, 0, sizeof a)
C(f); C(l); C(c); C(id); C(s); C(cnt); C(num); tot=0;
newnode(); newnode(-1); f[0]=1; n=0; all=0; dif=0; last=0; s[0]=-1;
}
int getf(int x) { while(s[n]!=s[n-l[x]-1]) x=f[x]; return x; }
void add(int x) {
s[++n]=x;
int q=getf(last);
if(!c[q][x]) {
int now=c[q][x]; now=newnode(l[q]+2);
f[now]=c[getf(f[q])][x];
c[q][x]=now;
num[now]=num[f[now]]+1;
}
last=id[n]=c[q][x];
x=c[q][x];
if(!cnt[x]) ++dif;
for(; x; x=f[x]) ++cnt[x], ++all;
}
void addstr(char *s) { for(; *s; ++s) add(*s-'a'); }
int getall() { return all; }
int getdif() { return dif; }
int getnum(int x) { return num[id[x]]; }
int getcnt(int x) { return cnt[id[x]]; }
void D() { for(int i=0; i<tot; ++i) printf("%d : f=%d cnt=%d num=%d len:%d
", i, f[i], cnt[i], num[i], l[i]); }
};
int main() {
return 0;
}