【算法】后缀自动机SAM

【Right集合】

后缀自动机真正优于后缀树的方面在于：结合了有限状态自动机，从而实现了O(n)的时空复杂度。

trans(s,str)表示s+str到达的状态。

ST(str)=trans(init,str)即包括了str这一子串的唯一状态（一个子串只能属于一个状态）

定义字符串a在S中出现的右端点位置集合Right(a)=r₁,r₂...r_n。

SAM中一个状态s的Right集合为Right(s)，那么状态s表示所有[Right(a)=Right(s)的子串a]，那么实际上状态s表示的子串a的长度在一个区间内，记作[Min(s),Max(s)]。字符串越短，Right集合越大。

容易证明对于任意状态a和b，Right(a)和Right(b)要么包含要么不相交。（很显然的结论，只是论文的证明比较严格化）

★在后缀自动机中，一个状态s（或称“节点s”）表示的是Right(a)=Right(s)的若干子串a，其长度区间为[MIn(s),Max(s)]，从而达到状态数O(n)的目的。

Right集合形成的树形包含关系称为Parent Tree，树边由孩子指向父亲，是SAM中的失配边。

Parent树从上往下，子串长度扩大，Right集合变小，父节点的Right集合包含子节点的Right集合。

fa=Parent(s)当且仅当fa是使Right(fa)最小且满足Right(s)?Right(fa)的结点，（从儿子到父亲，就是子串稍微缩短，Right集合变大）

另有Max(fa)=Min(s)-1，实质上是要求fa和s之间没有一个Right子集x满足Right(s)?Right(x)?Right(fa)。

【线性构造SAM】

线性构造采用增量法，即已知字符串T的SAM(T)，L=Len(T)，在末尾加入字符x，构造SAM(Tx)，转移如下：

①实边转移规则：t=trans(s,x)表示s--->t标号为x的边，若Right(s)={r1,r2...rn}，则Right(t)={r_i+1|s[r_i+1]=x}。

②虚边转移规则：Parent树边满足Right(s)?Right(fa)，Max(fa)=Min(s)-1（含义如上所述）

加入x，考虑所有Right集合包含L的结点v1,v2...vk，显然它们在Parent树上是一条从根到叶子的链。

定义叶子结点v1=p=ST(T)（即p代表整个串），Right(p)={L}，不妨它们从后代到祖先排为v1=p...vk=root。

同时新建结点np=ST(Tx)，Right(np)={L+1}。

考虑节点v，Right(v)={r1,r2...rn=L}

根据转移规则①，如果除了rn外不存在S[ri+1]=x，那么节点v不存在trans(v,x)。

根据转移规则②，越往上Right集合逐渐扩大直至节点vp存在trans(vp,x)，那么v₁~v_p-1只须向np连出标号为x的边（np=trans(v,x)），而vp~vk都已经存在trans(v,x)。

令trans(vp,x)=q，当Max(q)=Max(vp)+1时，只须在q的Right集合中插入L+1。

下面重点讨论Max(q)>Max(vp)+1的情况。