【自动机】
有限状态自动机的功能是识别字符串，自动机A能识别字符串S，就记为$A(S)$=true，否则$A(S)$=false。
自动机由$alpha$（字符集），$state$（状态集合），$init$（初始状态），$end$（结束状态集合），$trans$（状态转移函数）组成。
令$trans(s,str)$表示当前状态是$s$，读入字符串或字符$str$后达到的状态。
从状态$s$开始能识别的字符串$x$满足$trans(s,x)\subset end$。
【后缀自动机(SAM)】
SAM(suffix automaton)是一个能识别字符串$S$的所有后缀的自动机。
即$SAM(x)=true$，当且仅当$x$是$S$的后缀。
【有限状态后缀自动机】
有限状态后缀自动机是状态数最少的后缀自动机，大小为$O(n)$。
令$ST(a)=trans(init, a)$
如果字符串$a$在$S$中的$[l,r)$中出现，那么它就能识别$S$从$r$开始的后缀。
如果$a$在$S$中出现的位置为$\{[l_1, r_1),[l_2, r_2), ..., [l_n, r_n)\}$，那么$a$能识别的字符串为$\{suffix(r_1), suffix(r_2), ..., suffix(r_n)\}$。
令$right(a)={r_1, r_2, ..., r_n}$，那么$a$能识别的字符串完全由$right(a)$决定，也就是说如果$right(a)=right(b)$，则有$ST(a)=ST(b)$。
所以一个状态$s$，由所有right集合为$right(s)$的字符串组成。
只要给定一个$Right$集合，再给定一个长度，就确定了一个子串。
一个$Right$集合所对应的子串长度是一个区间，换句话说，如果对于一个$Right$集合，若长度$l$和$r$合适，则对于满足$l\leq x \leq r$的长度$x$也合适。因为如果$x$确定的子串$a_x$的某个出现位置不在$Right$集合中，那么$r$确定的子串$a_r$作为$a_x$的后缀，肯定也有某个位置不在$Right$中。如果$Righr$中的某个位置无法确定$a_x$，那么$a_x$作为$a_l$的后缀，也会有某个位置无法确定$a_l$。
于是令$[min(s), max(s)]$表示状态s的长度区间。
【状态数的线性证明】
假设两个状态$a, b$，假设$right(a)$和$right(b)$有交集。
因为$a,b$不同，所以这两个状态表示的子串无交集，$[min(a), max(a)]$和$[min(b), max(b)]$也无交集。因为如果有交集，那么他们的$Right$集合必定相等，就变成同一个状态了。
因为$right(a), right(b)$有交集，设$min(a)>max(b)$，那么$b$表示的所有子串长度都比$a$的小，而右端点相同，也就是说$b$中所有子串都是$a$中子串的后缀。也就是说$a$所出现的所有位置，$b$都出现了，所以$r_a\subset $r_b$，也就是$r_a$是$r_b$的真子集。
也就是说要么两个状态的$Right$集合不相交，要么其中一个状态的$Right$集合是另一个的真子集。
上方是所有状态的$Right$集合的示意图，我们称之为$Parent$树。
在这个树里，每个节点至少有两个儿子，所以节点的个数是$O(n)$的。
证明了节点数是$O(n)$的之后，我们还需要证明边数是$O(n)$的。
考虑一颗$SAM$的生成树（跟$Parent$树）无关。
令状态数为$M$，一共$M-1$条边，并且一个后缀对应自己遇到的第一条非树边（一条边可能对应多个后缀），刚好能够对应，而后缀个数为$O(n)$的，于是边数也是$O(n)$的。
我们不可能保存每一个状态的$Right$集合，但是一个状态的$Right$集合能由它子树中的叶子$Right$集合的并集。
对于一个状态$s$，设$r_i\in right(s)$，$right(trans(s,x))=\{r_i+1|S[r_i]==x\}$。
【线性构造SAM分析】
设当前字符串为$T$，$T$的长度为$L$，将新加入一个字符$x$。
设所有表示$T$的后缀（也就是$Right$中包含L）的状态$v_1, v_2, v_3, ...$
必然存在一个状态$p=ST(T)$满足$right(p)=\{L\}$，因为$v_1, v_2, v_3, ...$都包含$L$，所以他们在$Parent$树上全是$p$的祖先。
假设我们添加一个字符$x$后，用$np$表示$ST(Tx)$，那么$right(np)={L+1}$。
设$v1=p, v_2, .., v_k=root$，即按深度递减排序，所以$v_1, v_2, v_3, ...$的$Right$大小递增，且如果$v_i$的某位置出发有$x$的边，那么$v_{i+1}$也有。如果$v_j$出发没有$x$的边，那么直接可以把它向$np$连一条$x$的边，因为它的$Right$集合中有$L$。
设$v_p$是$v_1, v_2, v_3, ...$中第一个某个位置出发有$x$边的状态，令$trans(v_p, x)=q$，那么$right(q)=\{r_i+1|s[r_i]=x\}$，注意此时$x$还没有加进字符串里。
难点来了，$x$加进字符串里之后，我们不能直接在$right(q)$中加入$L+1$。
举例子:
$T=aaabaaaabaa$, $x=b$ 也就是$Tx=aaabaaaabaab$。
将$T$中$v_p$代表的某个字符串用括号标记：$a(aa)baa(aa)b(aa)$
将$T$中$q$代表的某个字符串用括号标记：$(aaab)a(aaab)aa$
此时加入$b$，会发现$L+1$加入后可以代表$aab$，但是不能代表$aaab$，所以并不能直接在$right(q)$中加入$L+1$。
当然如果$len(v_p)+1==len(q)$的话也是可以直接加入$L+1$的。
解决上面问题的方法就是新建一个节点$nq$，显然$right(nq)=right(q)\cup (right(np)=\{L+1\})$，就能够解决这个问题了。
于是$trans(v_p~v_k, x)=nq,trans(v_1~v_{p-1}, x)=q$，然后再连接一下$Parent$树就完成构造过程了。
【线性构造SAM步骤】
①新建节点$np$代表$ST(Tx)$。
②自$Parent$树的叶子节点$L$向上找到第一个有出边$x$的$Right$集合包含L的状态$v_p$，途中没有出边$x$的节点都向$np$连边，即$trans(v_1~v_{p-1}, x)=np$。
③若没有$v_p$，则$Parent$树上$np$连向$root$
④新建节点$nq$，复制一次$q$，并进行以下更新
$fa(nq)=fa(q)$//此时的$q$是加入$x$以前的$q$
$fa(q)=fa(np)=nq$
⑤$v_p~v_k$向$nq$连边，即$trans(v_p~v_k)=nq$。
然后就没有了。
注意点数是$2n$的！
代码如下：
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=, inf=1e9;
struct sam{int len, fa, trans[];}st[maxn];
int n, root, tott, now;
char s[maxn];
inline void read(int &k)
{
int f=; k=; char c=getchar();
while(c<'' || c>'') c=='-'&&(f=-), c=getchar();
while(c<='' && c>='') k=k*+c-'', c=getchar();
k*=f;
}
inline void extend(int ch)
{
int np=++tott, p=now;
st[np].len=st[p].len+; now=np;
while(p && !st[p].trans[ch]) st[p].trans[ch]=np, p=st[p].fa;
if(!p) st[np].fa=root;
else
{
int q=st[p].trans[ch];
if(st[p].len+==st[q].len) st[np].fa=q;
else
{
int nq=++tott;
st[nq]=st[q];
st[nq].len=st[p].len+;
st[np].fa=st[q].fa=nq;
while(p && st[p].trans[ch]==q) st[p].trans[ch]=nq, p=st[p].fa;
}
}
}
int main()
{
scanf("%s", s+);
n=strlen(s+); now=tott=root=;
for(int i=;i<=n;i++) extend(s[i]-'a');
}
拓展：http://blog.csdn.net/doyouseeman/article/details/52245413