Suffix Automaton 后缀自动机学习笔记

后缀自动机 Suffix Automaton (SAM)

定义

后缀自动机，本质上是关于单词的有向无环图，是一种强有力的数据结构，可以在$O(n)$的时间内构造完成并辅助解决很多字符串问题。它也可以被理解为一个长度为$N$的字符串的压缩之后存起来的信息。

后缀自动机是陈老师WJMZBMR首次引进国内OI圈的，陈老师的论文全是干货。

性质

一些说明

$Status(str)$表示$trans(init,str)$

$Reg(s)$表示从状态$s$开始可以识别的$string$(后缀集合)

下面这一段是关于$Reg(s)$的解释

什么是$Reg(s)$? 好问题!举个例子:

假设现在有一个串$S = “ABCABCBD”$

对于要在$S$中寻找的一个子串$S’ = “BC”$

很明显出现位置的集合为${ (2,3),(5,6)}$

他出现的后缀集合为${ suffix(3), suffix(6)}$

对于一个$string \space a$

$Reg(Status(a)) = \{ suffix(r_1),suffix(r_2) ... suffix(r_n)\}$

很明显我们只要存下了${r1,r2,…,rn}$ 就可以确定这个$Reg(Status(a))$

不妨用一个集合$Right(a)$来记录这一信息

性质1 对于两个子串$a,b$,如果$Right(a) = Right(b)$那么$Status(a) = Status(b)$

性质2 一个状态$s$表示的所有子串$Right$集合相同,为$Right(s)$.

所以说给定了一个$Right(s)$以及子串的长度我们就可以唯一确定这个子串$s$.

性质3 一个$Right$集合和一个长度定义了一个子串。

性质4 对于状态$s$，使得$Right(s)$合法的子串长度是一个区间，不妨定义为$[Min(s),Max(s)]$

性质5 $Right$集合的包含关系形成的树形结构叫做 Parent Tree

其他文献中叫做$Suffix Link$这个边是从孩子指向父亲的，和AC自动机的Fail Tree有点像

性质6 Parent树从上往下Right集合变小，子串长度变长

Parent Tree的叶子节点数$O(N)$，每个内部节点至少两个孩子，所以总结点数$O(N) $

~~差不多这些就已经够了？~~

一些推论

可以证明，在SAM中节点数不超过$2n−2$，边数不超过$3n−3$（包括转移边和Parent Tree的边）

性质7$Suffix Link$从父亲指向儿子后就是$Reverse(s)$ 的$Suffix Tree$ 反向字符串的后缀树！后缀树是一颗经过压缩的字典树

性质8 (感觉这个好神啊) 两个串的最长公共后缀,位于这两个串对应状态在$Parent$树上的最近公共祖先状态

其他还有一些可以发掘啊比如$Max$和$Min$的关系什么的…

建立SAM

$SAM$采用的是在线逐个加入字符的方法

简单来说分这几个阶段

假设当前$T$的串长度为$L$,现在新加入一个$x$

$p = Status(T),Right(p) = L$
新建一个$np = ST(T+x)$(加法为字符串的加法)

那么$p$的$Parent$祖先的$Right$集合里都有$L$

向上更新$trans(v,x)$,也就是没有字符$x$的祖先都需要更新,从这个状态$last$要向当前新状态$np$添加转移

也就是$trans[last].ch[x] = np$
分类讨论最后祖先的情况

(1)如果最后查找到了$root$,也就是根节点我们直接将它的$Parent$边连向$root$

(2)找到第一个有的祖先为$p$,令$q = trans[p].ch[x]$

再分类一波

(i)如果说满足了$t[q].val=t[p].val+1$ 说明强行加入这个$L+1$不会使得$Max(q)$减小直接连边

(ii)不满足我们考虑新建一个节点$nq$,$nq$本质上除了$Max$不同,其他信息均相同,将$np$,$q$的$parent$均连向$nq$

~~代码实现还是比较可读的吧…~~

Code

struct Sam{
    struct node{
        int ch[26],par,val; //par -> parent | val -> Max
    }t[N];
    int c[N],a[N],siz[N]; //这一行辅助数组
    int sz,root,last;
    inline void init(void){sz=root=last=1;} //定义根节点为1
    inline void ins(int x){
        int p=last,np=++sz;//新建一个节点
        t[np].val=t[p].val+1;//长度为上一个节点长度+1
        for(;p&&!t[p].ch[x];p=t[p].par) t[p].ch[x]=np;//向上祖先更改ch[x]
        if(!p) t[np].par=root;//如果最终为根节点直接将parent边连向root
        else{//分类讨论
            int q=t[p].ch[x];
            if(t[q].val==t[p].val+1) t[np].par=q;//满足Max(q) = Max(p) + 1
            else{
                int nq=++sz;//新建nq节点
                t[nq]=t[q];//拷贝节点q的信息
                t[nq].val=t[p].val+1;//nq和p唯一的不同Max
                t[q].par=t[np].par=nq;//也是拷贝信息
                for(;p&&t[p].ch[x]==q;p=t[p].par) t[p].ch[x]=nq;//拷贝信息
            }
        }
        last=np;
    }
    inline void calc(void){ //做其他事的时候可能会用
        for (int i = 1; i <= sz; ++i) c[t[i].val]++;
        for (int i = 1; i <= sz; ++i) c[i] += c[i-1];
        for (int i = 1; i <= sz; ++i) a[--c[t[i].val]] = i; //这里是基数排序对parent边作拓扑
    }
}sam;

题单

spoj8222 后缀自动机模板(spoj8222)

BZOJ3998 第K大子串，维护val和sum

NOI2015品酒大会 用后缀自动机建出后缀树，然后就变成了后缀树裸题

BZOJ4545 后缀自动机+有向LCT