后缀自动机(SAM)

搜了网上，多介绍应用，[3]算是一个比严格的定义性描述，并给出了证明。但是这个证明我并未看懂，下面综合一些资料给一些个人的直观但不失严谨的理解。

给定一个串A的后缀自动机是一个有限状态自动机(DFA)，它能够且仅能够接受A的后缀，并且我们要求它的状态数最少。

设n=|A|, 状态数:st=[n+1,2n-1], 边数:eg=[n,3n-4]。构造：空间复杂度:26*st, 时间复杂度O(3n)。查询:O(|q|);

可以看出，我们有可能把26*st优化到3*st的。

   先上图，有个直观认识：

<fig1>

这是表示串A="abaaaba"的后缀自动机，红色的S表示开始状态，红色的表示接受状态，黑色的表示非接受状态。从这个图可以看出，某个节点可以是多个节点的儿子，节省了状态空间。

定义：

状态p :=R(u)的等价类。其中R(u) := {u在A中出现位置右端点}。

比如上图中状态7识别两个后缀，满足R("aba") = R("ba")={3,7}。p称为接受状态是指自动机识别了一个从初始状态到p所表示的子串是A的后缀。

状态转移(p,c,q)表示状态p通过字符c转移到状态q。

后缀函数S(A,u):= u的最长后缀v,满足v不在u等价类中。

u=A时称为后缀链接，[3]引理1.5说S(A,A)=A中至少出现两次的最长后缀。

记最后一个加入的状态为last，则last,S(A,last), S(A,S(A,last),...组成接受状态构成的后缀路径SP。注意的是其他非接受状态的后缀链接也可以指向某个接受状态。 后缀链接指向上一个可以接受后缀的结点

长度函数L(A,p):= 初始状态到p的最长路径长度。即从根节点走到该节点,最多需要多少步。

下面我们考察状态机A增加一个字符x后，A的状态变化。

令z是A出现的且是Ax的最长后缀, zp是A中最长子串且zp,z属于A的同一等价类。

推论2.3.12说，如果x不在A中，则A的等价类在Ax中不变。(I)

推论2.3.11说，如果z=zp, 则A的等价类在Ax中不变。(II)

定理2.3.10说，如果z!=zp,则A中与z的等价类在Ax要改成zp。(III)

例子，  如下图，A="ccccbbccc", x=‘d‘对应(I),S(Ax,Ax)="";

后缀链接没有必要显示画出来，因为观察SP，就知道是9->3->2->1->0。

x=‘c‘对应(II),z="cccc", R(z)={4}, zp=z, S(A,A)="ccc", S(Ax,Ax)=z;

x=‘b‘对应(III),z="cccb",R(z)={5}=R(zp)，zp="ccccb", S(Ax,Ax)=z。

<fig2>

增量构造法:

设当前串为A,加入字符为x。

令p为R(A)={L(A)}对应的状态, 新节点np为R(Ax)={L(A)+1}对应的状态。

np显然应该是Ax的一个接受状态，np应该挂接到哪个位置呢？

为了节省状态空间，我们应该尽可能公用公共前缀，且尽可能让图宽以降低路径长度。

因此从last开始，沿着后缀链接跳，直到跳到第一个有x出边的v节点。

对p所有没有x出边的后缀链接v=S(A,p), trans(v,x)=np, 找第一个有x出边的v,令q=trans(v,x),

1. 如果L(q) = L(p)+1, p-->q只有由x可达，我们只需把q作为接受状态，到q的路径都是Ax的后缀。

2. 如果L(q)!=L(p)+1, p-->q就可能有其他若干字符可达，虚拟一个节点nq表示1的情形，把q,np的S都指向nq。

核心代码只有20行（估计后缀树代码量要大很多，这也是SAM的优势之一）：

    void add(int x)                                                                                                                                                              
    {
        State p = last, np = new State(); 
        np.val = last.val + 1;
        for(; (p != null) && (p.go[x] == null); p = p.fa)
            p.go[x] = np; 
        if(null == p){
            np.fa = root; 
        }else{
            State q = p.go[x]; 
            if(q.val == p.val + 1){
                np.fa = q; /*S(np)=q*/
            }else{
                State nq = new State();
                nq.copy(q); /*trans(nq,*)=trans(q,*)*/
                nq.val = p.val + 1;
                q.fa = np.fa = nq;
                for(; (p != null) && (p.go[x] == q); p = p.fa)
                    p.go[x] = nq; 
            }
        }
        last = np;
    }

Todo

我发现后缀链接很像KMP的向后跳。整理代码用模式串构造SAM，下周整理出来。

Ref

[1] 加速2,3 https://www.cs.duke.edu/courses/fall12/compsci260/resources/suffix.trees.in.detail.pdf

[2]后缀指针构造

http://marknelson.us/1996/08/01/suffix-trees

[3] Algebraic Combinatorics On Words.pdf

http://www.ctzsm.com/%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA%E6%8A%A5%E5%91%8A/