在回答什么是suffix auto machine前我们需要先知道什么是auto machine。
什么是自动机？一个FSN（有限状态自动机）就是一个具有识别字符串S对于自动机A是true还是false；即当s属于alpha，判断trans（state，ch）是否等于end；
同时令 trans( state,str ) 表示当前状态是 s ，在读入字符串 str 之后，所到达的状态。 而一个sam就是一个能够识别字符s所有后缀的自动机。 我们可以像AC自动机一样，在trie上建立sam，但显然对于长度为N的串可能有N^2个结点；能不能优化呢？ 我们可以先空想一个假设存在一个叫最简状态后缀机的东西，在还没有构造出这个东西前我们可以先看看它会有什么性质。 设有一母串S，它的所有后缀集合为suf，设从a开始的后缀为suffix（a），定义st（str）=trans（init，str），reg（st（a））为st（a）能识别出的字符串集； 性质一：若串s不属于suf则st（s）=null； 性质二：若串s属于suf则st（s）！=null； 推论1：x能被自动机识别当且仅当x属于suf； 推论2:st（a）能识别x当且仅当ax属于suf；
推论3:如果a在s的范围为【l，r）则st（a）能识别S从r开始的后缀； 推论4:如果a在s的范围集合为【L1，R1），【L2，R2），【L3，R3）。。。【Ln，Rn），则st（a）能识别以R1，R2，R3.。。Rn开始的后缀,设right（a)={R1,R2,R3...Rn}; 性质三：若对两个串a，b属于fac，且right（a）=right（b），则st（a）=st（b），所以状态s可以简化为所有right集合为right（s）的串的公共母串； 性质四：若r属于right（s），且已知子串长度len，则该子串为S【r-len，r），且显然长度len的可选范围为一个区间，则可令s的区间为【min（s），max（s）】； 这时最简状态后缀机的线性性就显然了； 而我们可以用简化后的right集合构建一颗树，不妨取名parent，则显然max（fa（s））=min（s）-1； 显然以转移方式建树的边也不会超过o（n）； 由于父亲的right集是它的后代的所有right集的并集，所以我们可以用树的dfs序排列建树； 下面是kuangbin的后缀自动机板子；
structSAM_Node
{
SAM_Node*fa,*next[CHAR];intlen;
intid,pos;
SAM_Node(){}
SAM_Node(int_len){
fa= 0;
len= _len;memset(next,0,sizeof(next));
}};
SAM_NodeSAM_node[MAXN*2], *SAM_root, *SAM_last;intSAM_size;
SAM_Node*newSAM_Node(intlen)
{
SAM_node[SAM_size] =SAM_Node(len);SAM_node[SAM_size].id= SAM_size;return&SAM_node[SAM_size++];
}
SAM_Node*newSAM_Node(SAM_Node*p){
SAM_node[SAM_size] = *p;SAM_node[SAM_size].id= SAM_size;return&SAM_node[SAM_size++];
}
voidSAM_init(){
SAM_size = 0;
SAM_root = SAM_last = newSAM_Node(0);SAM_node[0].pos= 0;
}
voidSAM_add(intx,intlen){
SAM_Node*p = SAM_last, *np = newSAM_Node(p->len+1);np->pos= len;
SAM_last = np;for(;p && !p->next[x];p = p->fa)p->next[x] = np;
if(!p){
np->fa= SAM_root;
return;}
SAM_Node*q = p->next[x];if(q->len== p->len+ 1){
np->fa= q;
return;}
SAM_Node*nq = newSAM_Node(q);nq->len= p->len+ 1;
q->fa= nq;
np->fa= nq;
for(;p && p->next[x] == q;p = p->fa)p->next[x] = nq;
}
voidSAM_build(char*s){
SAM_init();
intlen =strlen(s);for(inti = 0;i < len;i++)
SAM_add(s[i] -'a',i+1);
}
//加入串后进行拓扑排序。charstr[MAXN];
inttopocnt[MAXN];SAM_Node*topsam[MAXN*2];
intn =strlen(str);SAM_build(str);memset(topocnt,0,sizeof(topocnt));for(inti = 0;i < SAM_size;i++)
topocnt[SAM_node[i].len]++;for(inti = 1;i <= n;i++)
topocnt[i] += topocnt[i-1];for(inti = 0;i < SAM_size;i++)
topsam[--topocnt[SAM_node[i].len]] = &SAM_node[i];
好了。。。拜拜～～
