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;