[ Suffix Automaton ] 後綴自動機

定義字串S的後綴自動機是一種自動機可以接受S的所有後綴，其狀態最多為2*strlen(s)-1個，雖然理論複雜，但其構造方式十分簡單，且它可以用來處理一些後綴數組或事後綴樹的問題，因此是一個十分強大的資料結構。
後綴自動機大致的構造方式是將字串擔一字元按順序進行插入，插入的均攤時間為$\ord 1$，關於詳細的情形可以在 http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html 這個網站中得到
而關於複雜度及詳細的證明請參考陈立杰的簡報
關於狀態數為線性的證明在19~21頁，有詳細的圖文解說
這個網站包含其一些延伸資料結構http://maskray.me/blog/2013-05-10-suffix-automaton
為了減少記憶體的使用，以vector代替指標維護狀態
以下提供模板:

	#ifndef SUFFIX_AUTOMATON
	#define SUFFIX_AUTOMATON
	#include<vector>
	template<char L='a',char R='z'>
	struct suffix_automaton{
	struct node{
	int ch[R-L+1],fa,len;
	node(int l=0):fa(0),len(l){
	for(int i=0;i<=R-L;++i)ch[i]=0;
	}
	};
	std::vector<node >S;
	int tail,u,v,np,vp;
	suffix_automaton():S(2),tail(1){S[0].fa=0;}
	inline void add(int c){
	c-=L;
	u=tail;
	S.push_back(node(S[u].len+1));
	tail=np=S.size()-1;
	for(;u&&!S[u].ch[c];u=S[u].fa)S[u].ch[c]=np;
	if(!u)S[np].fa=1;
	else{
	v=S[u].ch[c];
	if(S[v].len==S[u].len+1)S[np].fa=v;
	else{
	S.push_back(S[v]);
	vp=S.size()-1;
	S[vp].len=S[u].len+1;
	S[v].fa=S[np].fa=vp;
	for(;u&&S[u].ch[c]==v;u=S[u].fa)S[u].ch[c]=vp;
	}
	}
	}
	inline int size(){return S.size()-2;}
	};
	#endif

view raw Suffix Automaton.cpp hosted with ❤ by GitHub