SAM，即Suffix Automaton，后缀自动机。

关于字符串有很多玩法，有很多算法都是围绕字符串展开的。为什么？我的理解是:相较于数字组成的序列，字母组成的序列中每个单位上元素的个数是有限的。对于有限的东西，相较于无限的东西就会具有一些奇妙的性质。最简单的，就是序列扩展成的树每个节点的儿子数是有限的。所以根据这个，从字符串Hash，到KMP，再到Suffix Array,Suffix Automaton，纷纷诞生。

后缀数组在处理字符串上相当于一把好钢，他能应付在字符串的大多数问题。那么为什么还要学SAM，很简单。SAM很有用，而且很短。优雅而有用，这就是要学的原因。

如果不说没用的话就是这玩意不容易写崩，而且可以直接构造后缀数组。

具体的细节不深究，搞OI的讲实用，所以这里面值谈构造与应用，以题为主。

构造

众所周知，后缀数组的编写很糟心，常数也比较大。但是SAM好就好在他可以在线构造。

先放代码：

struct SAM{	int pre[MAXN],son[MAXN][26],cnt,len,now,step[MAXN],np,nq,p,q;	SAM(){		memset(pre,0,sizeof(pre));		memset(son,0,sizeof(son));		cnt=1;len=0;now=1;	}	void Extend(int nxt){		p=now;np=++cnt;		step[np]=step[now]+1;		now=np;		while(p&&!son[p][nxt]){			son[p][nxt]=np;			p=pre[p];		}		if(!p)pre[np]=1;		else{			q=son[p][nxt];			if(step[q]==step[p]+1)pre[np]=q;			else{				step[(nq=++cnt)]=step[p]+1;				memcpy(son[nq],son[q],sizeof(son[q]));				pre[nq]=pre[q];				pre[np]=pre[q]=nq;				while(p&&son[p][nxt]==q){					son[p][nxt]=nq;					p=pre[p];				}			}		}	}	int Walk(int nxt){		while(!son[now][nxt]&&pre[now]){			now=pre[now];			Len=step[now];		}		if(!son[now][nxt])return 0;		now=son[now][nxt];Len++;		return Len;	}	void Build(){		scanf("%s",s+1);		int len=strlen(s+1);		up(i,1,len)Extend(s[i]-‘a‘);	}}sam;

SAM初探