寫在前面
最近無意中看到了這個資料結構，順便也就學習了一下。
而且發現網上關于這個算法的描述有很多地方是錯的，在這裡做了一些更正。
處理字元串的算法很多：KMP,E-KMP,AC自動機,字尾三兄弟:字尾樹、字尾數組、字尾自動機,Trie樹、Trie圖,符串hash...
但以上資料結構在處理回文串上還是稍有欠缺，用這些來處理回文顯得太小題大做。
Manacher算法可以在O(n)時間内處理出S串每個位置的最長回文串，但如果要統計S串中有多少回文串，
或者S串的所有子串的回文串的個數,那麼就要用到一種和Manacher一樣優雅的資料結構：回文自動機。
一.What Is Palindromic auto-machine?
這是一種比較新的資料結構，在原文中已有詳細介紹與代碼實作。
回文樹其實不是嚴格的樹形結構，因為它有是兩棵樹，分别是偶數長度的回文樹和奇數長度的回文樹，樹中每個節點代表一個回文串。
為了友善，第一棵樹的根是一個長度為0的串，第二棵就是為-1的串，不要感到奇怪，就是-1。
可以證明，最多隻有n個結點（n是串的長度）。這個可以用Manacher算法來證明。
如果某結點代表的是串ccabacc，那麼它的父親代表的串就是去掉前後兩個字元cabac。
每個點還有一個fail指針，表示這個串的字尾中最長的回文串，比如babab的fail指向bab，bab的指向b。
方法的思想和KMP，AC自動機很類似，如果你了解了KMP與AC自動機，那麼這個算法基本可以一看就懂。
資料說明
len[i]:節點i的回文串的長度
next[i][c]：節點i的回文串在兩邊添加字元c以後變成的回文串的編号(和字典樹的next指針類似)
fail[i]：類似于AC自動機的fail指針，指向失配後需要跳轉到的節點
cnt[i]：節點i表示的回文串在S中出現的次數（建樹時求出的不是完全的，count()加上子節點以後才是正确的）
num[i]：以節點i回文串的末尾字元結尾的但不包含本條路徑上的回文串的數目。(也就是fail指針路徑的深度)
last：指向最新添加的回文結點
S[i]表示第i次添加的字元
p表示添加的節點個數
二.How To Build Palindromic auto-machine?
注：以下部分圖檔來自網際網路
假設現在我們有串S='abbaabba'。
首先我們添加第一個字元'a'，S[++ n] = 'a'，然後判斷此時S[n-len[last]-1]是否等于S[n]
即上一個串-1的位置和新添加的位置是否相同，相同則說明構成回文，否則，last=fail[last]。
此時last=0，我們發現S[1-0-1]!=S[1]，是以last=fail[last]=1，
然後我們發現S[1-(-1)-1]==S[1]（即自己等于自己，是以我們讓len[1]等于-1可以讓這一步更加友善）。
令cur等于此時的last（即cur=last=1），判斷此時next[cur]['a']是否已經有後繼，
如果next[cur]['a']沒有後繼，我們就進行如下的步驟：
建立節點（節點數p++，且之後p=3），并讓now等于新節點的編号（now=2），
則len[now]=len[cur]+2（每一個回文串的長度總是在其最長子回文串的基礎上在兩邊加上兩個相同的字元構成的，是以是+2，
同時展現出我們讓len[1]=-1的優勢，一個字元自成一個奇回文串時回文串的長度為(-1)+2=1）。
然後我們讓fail[now]=next[get_fail ( fail[cur] )]['a']，即得到fail[now]（此時為fail[2] = 0），
其中的get_fail函數就是讓找到第一個使得S[n-len[last]-1]==S[n]的last。然後next[cur]['a'] = now。
當上面步驟完成後我們讓last = next[cur][c]（不管next[cur]['a']是否有後繼），然後cnt[last] ++。
此時回文樹為下圖狀态：
現在我們添加第二個字元字元'b'到回文樹中：
繼續添加第三個字元'b'到回文樹中：
繼續添加第四個字元'a'到回文樹中：
繼續添加第五個字元'a'到回文樹中：
繼續添加第六個字元'b'到回文樹中：
繼續添加第七個字元'b'到回文樹中：
繼續添加第八個字元'a'到回文樹中：
到此，串S已經完全插入到回文樹中了，現在所有的資料如下：
然後我們将節點x在fail指針樹中将自己的cnt累加給父親，從葉子開始倒着加，最後就能得到串S中出現的每一個本質不同回文串的個數。
構造回文樹需要的空間複雜度為O（N*字元集大小），時間複雜度為O（N*log（字元集大小）），這個時間複雜度比較神奇。如果空間需求太大，可以改成鄰接表的形式存儲，不過相應的要犧牲一些時間。
三.The Use Of Palindromic auto-machine
1.求串S字首0~i内本質不同回文串的個數（兩個串長度不同或者長度相同且至少有一個字元不同便是本質不同）
2.求串S内每一個本質不同回文串出現的次數
3.求串S内回文串的個數（其實就是1和2結合起來）
4.求以下标i結尾的回文串的個數
四.some problem
五.Template code
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-19-21.48
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 100005 ;
const int N = 26 ;
char s[MAXN];
struct Palindromic_Tree
{
int next[MAXN][N] ;//next指針，next指針和字典樹類似，指向的串為目前串兩端加上同一個字元構成
int fail[MAXN] ;//fail指針，失配後跳轉到fail指針指向的節點
int cnt[MAXN] ;
int num[MAXN] ; // 目前節點通過fail指針到達0節點或1節點的步數(fail指針的深度)
int len[MAXN] ;//len[i]表示節點i表示的回文串的長度
int S[MAXN] ;//存放添加的字元
int last ;//指向上一個字元所在的節點，友善下一次add
int n ;//字元數組指針
int p ;//節點指針
int newnode(int l) //建立節點
{
for(int i = 0 ; i < N ; ++ i) next[p][i] = 0 ;
cnt[p] = 0 ;
num[p] = 0 ;
len[p] = l ;
return p ++ ;
}
void init() //初始化
{
p = 0 ;
newnode(0) ;
newnode(-1) ;
last = 0 ;
n = 0 ;
S[n] = -1 ;//開頭放一個字元集中沒有的字元，減少特判
fail[0] = 1 ;
}
int get_fail(int x) //和KMP一樣，失配後找一個盡量最長的
{
while(S[n - len[x] - 1] != S[n]) x = fail[x] ;
return x ;
}
void add(int c,int pos)
{
printf("%d:",p);
c -= 'a';
S[++ n] = c ;
int cur = get_fail(last) ; //通過上一個回文串找這個回文串的比對位置
printf("%d ",cur);
if(!next[cur][c]) //如果這個回文串沒有出現過，說明出現了一個新的本質不同的回文串
{
int now = newnode(len[cur] + 2) ; //建立節點
fail[now] = next[get_fail(fail[cur])][c] ; //和AC自動機一樣建立fail指針，以便失配後跳轉
next[cur][c] = now ;
num[now] = num[fail[now]] + 1 ;
for(int i=pos-len[now]+1; i<=pos; ++i) printf("%c",s[i]);
} last = next[cur][c] ;
cnt[last] ++ ;
putchar(10);
}
void count()
{
for(int i = p - 1 ; i >= 0 ; -- i) cnt[fail[i]] += cnt[i] ;
//父親累加兒子的cnt，因為如果fail[v]=u，則u一定是v的子回文串！
}
} run;
int main()
{
scanf("%s",&s);
int n=strlen(s);
run.init();
for(int i=0; i<n; i++) run.add(s[i],i);
run.count();
return 0;
}