后缀自动机初步

摘要

在 XRY 大佬倾力指点下,我学会了 SAM,也是很神仙了

后缀自动机(Suffix Automaton)是能够识别某一字符串的后缀的自动机,在处理后缀与子串问题上有广泛的运用

后缀自动机

形式化定义

后缀自动机是一种有限状态自动机,对于一个 SAM,其转移函数是以字符集 为转移条件,将当前状态 转移到另一状态 的函数 .

这个状态分两种:合法与不合法。说白了就是存在和不存在。如果一个字符串不被 SAM 接受,那么 就会转移到空指针。初始状态是根结点,也就是字符串开头

小性质

SAM 的空间复杂度与建立的时间复杂度是

建立的后缀自动机能够接受 的所有子串。道理很简单, 的子串一定是其某一后缀的前缀

不同于 AC 自动机,后缀自动机是一个 DAG

构造 SAM

详细过程请见 OI-WIKI,本文笔者只记录大致思路

后缀自动机中的每一个状态对应了一类子串,这一类子串长度个不相同,并且按长度排序后前一个是后一个的后缀。

等价类

我们假设这一类子串中最长的子串是 ,那么这一类子串满足这样的关系: 的后缀在 S 中的出现的位置是相同的。这类字符串被称为等价类。

包含类

还有一种情况,就是 S 的某一子串 的后缀 在 S 中出现的位置比 多,那么称 的包含类。为什么包含?因为 出现的位置 一定出现,而 出现的位置 不一定出现

Parent 树

SAM 除了构建自动机还会构建一个 parent 树,parent 树中,当前状态的父结点总是它的包含类,即它的某个后缀形成的等价类。结合等价类和包含类,使得 SAM 的空间复杂度降到了线性级别

模板

const int N=2e6+6,LT=30;
struct SAM{
    int tot,last;
    int tr[N][LT],len[N],link[N];
    SAM(){tot=last=1;}// 初始化
    void insert(int x){
        int u=++tot,p=last;// 新建结点,p 是在 link 上跳指针用的
        len[u]=len[last]+1,last=u;
        while(p&&tr[p][x]==0)tr[p][x]=u,p=link[p];// 更新 last 在 link 树上的祖先的转移函数
        // 接下来,我们求新建结点 u 的 link 指针,同时会更新 link 树
        if(!p)link[u]=1;// 跳到根结点的 link
        else {int q=tr[p][x];
            if(len[q]==len[p]+1)link[u]=q;
            else{
                // 如果不是 0,说明结点 p 在之前就存在字符 x 的转移函数
                // 那么就考虑这个转移到达的状态是否是等价类
                // 如果是等价类,那么 link 就指向 q;
                // 否则就要从中分离出一个包含类,然后指向这个结点
                int cq=++tot;
                len[cq]=len[p]+1,link[cq]=link[q];
                memcpy(tr[cq],tr[q],sizeof(tr[q]));
                link[u]=link[q]=cq;
                while(p&&tr[p][x]==q)tr[p][x]=cq,p=link[p];
            }
        }
    }
}

SAM 的应用

匹配子串

显然的,只要转移过程中没有跳到空指针,就说明状态合法。

若匹配的子串为 ,那么复杂度 .

本质不同的子串个数

这道题本来可以用后缀数组做,即总数减 h 数组;

不过放在 SAM 上也是能做的。SAM 是一个 DAG, 的每一个子串都对应 SAM 中从起点开始的一条路径。那么我们求路径条数即可。定义 表示从 开始的路径数量。

复杂度 .

所有不同子串的总长度

根据上一个应用,再记录一个总长度值 ,跟着一起转移即可

复杂度 .

字典序第 k 小子串

多组询问,查询所有子串中字典序第 k 小的子串。

根据 3.2,我们利用 ,按字典序遍历当前结点的下一个状态,然后查看前 k 小是否被包含

复杂度 .

参考文献

OIWIKI. 后缀自动机 (SAM). https://oi-wiki.org//string/sam/


  转载请注明: Sshwy's Blog 后缀自动机初步

 上一篇
筛法自闭 筛法自闭
摘要 tqy 奆奆继续给我们讲数论啦 洲阁筛待更 数论函数与积性函数数论函数,积性函数,完全积性函数的定义、性质 常见数论函数 SPOJ DIVCNT1 \sum_{i=1}^n\sigma(i)\\ =\sum_{i=1}^n\sum_
2019.02.14
下一篇 
概率期望小结 概率期望小结
摘要 Tqy 奆奆给我们讲概率啦 概率与期望概率空间三元组 . 被称为概率空间: 样本空间 是一个非空集合 集合 的元素是 的子集, 是样本空间 $\Omeg
2019.02.13
  目录