SAM（Suffix Automaton），后缀自动机。

SAM是种十分神奇的数据结构，我认为他的主要神奇之处，在于最大限度的利用了分类思想。

SAM上有两种边，代表两种转移方式。

一种是树边，一种是转移边，树边代表对SAM对子串出现位置的分类，转移边代表当前节点代表的子串加入字符后的节点的分类。

由于子串的出现位置的集合或者是子集关系，或者无交集，可以证明状态数是O(n)的。

在有了这些东西后，SAM基本可以搞出关于字符串的所有问题。

SAM有句很经典的话：出现次数向父亲传递，接收串数从儿子获取。

 

构造模板：

struct sam{	int pre[maxn],c[maxn][26],len[maxn],q,p,nq,np;	int cnt,now;	sam(){mem1(pre,0);mem1(c,0);mem1(len,0);cnt=now=1;}	void expend(int x){		p=now,np=++cnt;		len[np]=len[now]+1;now=np;		while(p&&!c[p][x])c[p][x]=np,p=pre[p];		if(!p)pre[np]=1;		else {			q=c[p][x];			if(len[q]=len[p]+1)pre[np]=q;			else {				len[nq=++cnt]=len[p]+1;				mem2(c[nq],c[q]);				pre[nq]=pre[q];				pre[np]=pre[q]=nq;				while(p&&c[p][x]==q)c[p][x]=nq,p=pre[p];			}		}	}	void build(char* s){		int n=strlen(s+1);		up(i,1,n)expend(s[i]);	}}SAM;