[ Palindromic Tree ] 回文樹(回文自動機)

回文樹是去年新出的資料結構，由一個俄羅斯codeforces的紅人Mikhail Rubinchik在2014年發明的(http://codeforces.com/blog/entry/13959)，雖然名子直接翻譯叫回文樹，但他長的比較像一個自動機，所以也有很多人翻回文自動機。
在構造它之前，我們必須先證明一個長度n的字串其不同的回文子字串個數<=n，什麼是不同的回文子字串?就是長的不同的回文子字串，及把出現位置不同但形狀一樣的回文子字串當做是同樣的子字串。

證明:

1. 由左往右一個一個增加字符，則新產生的回文子字串其結尾一定是當前增加的字符x
2. 考慮以當前位置為結尾的最長回文x......x，顯而易見的，若產生除了x......x之外其它的回文子串，則必定被x......x所包含
3. 若增加字符x後，產生了除了x......x之外其它的回文子串，則根據回文的性質，其一定早已在x......的部分理出現(例:假設S是對稱點x...S.xax，因為回文的性質所以S的另一邊也會出現相同的字串xax.S.xax)
4. 因此每增加一個字符最多只會產生一個新的回文子字串，而長度為n的字符串最多只會產生n種不同的回文子字串

接下來進行回文自動機元素的詳細解說:

回文自動機包含以下元素:

1. 狀態St，所有節點的集合，一開始兩個節點，0表示偶數長度串的根和1表示奇數長度串的根
2. last 新增加一個字符後所形成的最長回文串的節點編號
3. s 當前的字符串(一開始設s[0]=-1(可以是任意一個在串S中不會出現的字符))
4. n 表示添加的字符個數

每個節點代表一個不同的回文子字串，我們在每個節點會儲存一些數值:

1. len 表示所代表的回文子字串長度
2. next[c] 表示所代表的回文子字串在頭尾各增加一個字符c後的回文字串其節點編號
3. fail 表示所代表的回文子字串不包括本身的最長後綴回文子串的節點編號
4. cnt(非必要) 表示所代表的回文子字串在整體字串出現的次數(在建構完成後呼叫count()才能計算)
5. num(非必要) 表示所代表的回文子字串其後綴為回文字串的個數

注意一開始必須先將狀態初始化St[0].len=0，St[1].len=-1，last=0，s[0]=-1，n=0

關於構造方法及圖片說明請參考:http://blog.csdn.net/u013368721/article/details/42100363
概念請參考:http://blog.csdn.net/MaticsL/article/details/43651169
證明請參考:http://yqcmmd.com/index.php/2015/03/30/746/

最後提供模板(使用STL vector)，因為St的元素在解題的過程中常會被用到所以就不封裝了:

	#ifndef PALINDROMIC_TREE
	#define PALINDROMIC_TREE
	#include<vector>
	struct palindromic_tree{
	struct node{
	int next[26],fail,len;/*這些是必要的元素*/
	int cnt,num;/*這些是額外維護的元素*/
	node(int l=0):fail(0),len(l),cnt(0),num(0){
	for(int i=0;i<26;++i)next[i]=0;
	}
	};
	std::vector<node >St;
	std::vector<char >s;
	int last,n;
	palindromic_tree():St(2),last(1),n(0){
	St[0].fail=1;
	St[1].len=-1;
	s.push_back(-1);
	}
	inline void clear(){
	St.clear();
	s.clear();
	last=1;
	n=0;
	St.push_back(0);
	St.push_back(-1);
	St[0].fail=1;
	s.push_back(-1);
	}
	inline int get_fail(int x){
	while(s[n-St[x].len-1]!=s[n])x=St[x].fail;
	return x;
	}
	inline void add(int c){
	s.push_back(c-='a');
	++n;
	int cur=get_fail(last);
	if(!St[cur].next[c]){
	int now=St.size();
	St.push_back(St[cur].len+2);
	St[now].fail=St[get_fail(St[cur].fail)].next[c];
	/*不用擔心會找到空節點，由證明的過程可知*/
	St[cur].next[c]=now;
	St[now].num=St[St[now].fail].num+1;
	}
	last=St[cur].next[c];
	++St[last].cnt;
	}
	inline void count(){/*cnt必須要在構造完後呼叫count()去計算*/
	std::vector<node>::reverse_iterator i=St.rbegin();
	for(;i!=St.rend();++i){
	St[i->fail].cnt+=i->cnt;
	}
	}
	inline int size(){/*傳回其不同的回文子串個數*/
	return St.size()-2;
	}
	};
	#endif

view raw Palindromic Tree.cpp hosted with ❤ by GitHub