首页 > 其他分享 >【学习笔记】 字符串基础 : 后缀自动机(基础篇)

【学习笔记】 字符串基础 : 后缀自动机(基础篇)

时间:2024-04-19 11:15:48浏览次数:16  
标签:ch mathbf 后缀 text 基础 link endpos 自动机

本文只介绍关于 \(\mathbf{SAM}\) 的基本概念与实现

后缀自动机是什么

类似 \(\text{AC}\) 自动机,后缀自动机(\(\text{SAM}\)) 是能且只能接收字符串所有后缀的自动机

我们首先要知道,\(\mathbf{SAM}\) 是只能接收所有后缀的结构而不是只能维护后缀的结构

事实上 \(\mathbf{SAM}\) 的主要作用是维护字符串 \(S\) 的每一个子串(因为一个 \(S\) 的子串一定是一个 \(S\) 的后缀的前缀)

在下文中我们将定义 \(\sum\) 为字符集, \(|\sum|\)为字符集大小

后缀自动机的定义

\(\text{SAM}\) 是一张 \(\text{DAG}\),节点被称作状态,边被称作转移

图中存在一个源点 \(t_0\) 称作初始节点,其他所有节点均可从 \(t_0\) 到达

每个边都标有一些字符,从一个节点出发的所有边都不同(也就是说没有相同的字母作为边)

存在至少一个终止的状态,从 \(t_0\) 出发最后转移到一个终止状态,那么路径上所有边链接起来一定是字符串 \(s\) 的一个后缀,每个字符串 \(s\) 的后缀都可以用一个 \(t_0\) 到某个终止状态的路径来构成

下文中我们定义以下内容

  • \(\text{endpos}\)

    代表一个串的结束位置

    image

    这样我们可以把子串根据 \(\text{endpos}\) 分为若干种的等价类

    我们可以得到几个重要引理(钦定 \(\left|u\right|\le \left|w\right|\))

    • 当字符串 \(u\) 在 \(s\) 中的每次出现,都是以 \(w\) 后缀的形式存在时,字符串 \(s\) 的两个非空子串 \(u\) 和 \(w\) 的 \(\text{endpos}\) 相同

      证明:

      • 若 \(u\) 和 \(w\) 的 \(\text{endpos}\) 相同,则 \(u\) 是 \(w\) 的一个只以 \(s\) 中的一个 \(w\) 的后缀的形式出现后缀

      • 若 \(u\) 为 \(w\) 的一个后缀且在 \(s\) 中出现时只以后缀的形式,两个子串的 \(\text{endpos}\) 相同。

      因此得证

    • \(u\) 和 \(w\) 的 \(\text{endpos}\) 集合要么不交,要么完全包含

      两者关系为 \(\begin{cases} \text{endpos}(w) \subseteq \text{endpos}(u) & u \small\text{ 是 } w \small \text { 的后缀}\\ \text{endpos}(w) \cap \text{endpos}(u) = \varnothing & \end{cases}\)

      证明:

      • 在 \(u\) 是 \(w\) 的后缀时,类似上图内的 “能够接收 \(\mathbf{ab}\) 的串的节点一定可以接受 \(\mathbf{b}\)”

      • 若集合 \(\text{endpos}(u)\) 与 \(\text{endpos}(w)\) 有至少一个公共元素,那么由于字符串 \(u\) 与 \(w\) 在相同位置结束,\(u\) 是 \(w\) 的一个后缀。

      • 所以在每次 \(w\) 出现的位置,子串 \(u\) 也会出现。所以 \(\text{endpos}(w)\subseteq \text{endpos}(u)\)

      因此得证

    • 将一个 \(\text{endpos}\) 等价类中的所有子串按长度非递增的顺序进行排序

      每个子串长度都小于等于它前一个子串且每个子串是它前一个子串的后缀

      因此对于同一等价类的任一两子串,较短者为较长者的后缀且类中的子串长度恰好覆盖整个区间 \([x,y]\) 。

  • \(\text{len}\)

    代表一个节点能控制的最大长度,比如当一个节点可以控制 \(a\) 和 \(ab\) 时其控制的最大长度( \(\text{len}\) )也就是 \(ab\) 代表的 \(2\)

  • \(\text{fa}\)

    一个节点其连接的 \(\text{fa}\) 节点是其的一个后缀,因为节点是按照 \(\text{endpos}\) 来分的,所以其的 \(\text{fa}\) 是其后缀内 \(\text{endpos}\) 集合不同的最长的后缀

后缀自动机的构建过程

假设要建立的串是 \(S=aabab\) ,我们先建立一条链

image

然后加入一些边来维护后缀自动机,让后缀自动机能够记录所有的后缀

image

再比如说要建立的串是 \(S=kevenhe\),那么建立出的后缀自动机形态为

image

我们发现,在第一个建立完毕的 \(\mathbf{ SAM }\) 内存在多个 \(\mathbf{ ab }\) 串,而如果我们查询 \(\mathbf{ ab }\) 串就只能查询到第一个出现的 \(\mathbf{ ab }\) 串(也就是先向右再向下)

因此我们需要引入一个名为 \(\mathbf{ parent }\) 树的数据结构来统计本质相同的子串

\(\mathbf{ parent }\) 树的建立

后缀链接 \(\mathbf{link}\)

对于 \(\mathbf{parent}\) 树,我们需要一个名为 \(\mathbf{ link }\) (后缀链接)的东西来维护

定义

考虑 \(\mathbf{SAM}\) 中某个不是 \(t_0\) 的状态 \(v\),\(v\) 对应于具有相同 \(\mathbf{endpos}\) 的等价类。

定义 \(w\) 为这些字符串中最长的一个,则所有其它的字符串都是 \(w\) 的后缀。

同时,字符串 \(w\) 的前几个后缀(按长度降序考虑)全部包含于这个等价类,且所有其它后缀在其它的等价类中。

记最长的这样的后缀为 \(t\),将 \(v\) 的后缀链接连到 \(t\) 上

一个 后缀链接 \(\mathbf{link}(v)\) 连接到对应于 \(w\) 的最长后缀的另一个 \(\mathbf{endpos}\) 等价类的状态

通过 \(\mathbf{endpos}\) 建立的树和通过 \(\mathbf {link}\) 建立的树形态是相同的
image

如上图

其中这些链接这些节点的边其实和后缀链接 \(\mathbf{link}\) 本质相同

我们可以发现最后建立的一定是一颗树的形状,其中根节点一定是 \(t_0\)

这棵树就是我们的 \(\mathbf{parent}\) 树了

定理

  • 设一个 \(\mathbf{endpos}\) 等价类为 \(\mathbf{E}\) ,\(\mathbf{E}\) 中最短的串为 \(s\) 。

    那么 \({\mathbf{endpos}(v)\subsetneq \mathbf{endpos}(\mathbf{link}(v))}\) (这里因为如果相等会合并为一个 \(\mathbf{endpos}\) 所以不能取等)

  • \(\mathbf{link}(\mathbf E)\) 中最长的串是 \(s\) 的长度为 \(|s|−1\) 的真后缀。

\(\mathbf{SAM}\) 的建造

我们把 \(\mathbf{parent}\) 树和最开始建出的 \(\mathbf{DAG}\) 放到一起就形成了 \(\textbf{SAM}\)

下面的是以 \(abcbc\) 为例建出的 \(\mathbf{SAM}\) 了

image

\(\mathbf{parent}\) 树与 \(\mathbf{DAG}\) 公用结点,但二者的边都是独有的

构造算法

下面的是 \(\mathbf{SAM}\) 的算法流程

初始化:\(\mathbf{len(t_0)}=0\),\(\mathbf{link(t_0)}=-1\)

  1. 令 \(last\) 为添加字符 \(\mathbf{ch}\) 之前整个字符串 \(S\) 所对应的结点(从 \(t_0\) 出发走到 \(last\) 的路径上边组成的字符串就是 \(S\) ,初始 \(last=0\) )。

  2. 创建一个新的状态 \(cur\) ,让 \(\mathbf{len(cur)} = \mathbf{len(last)}+1\)

  3. 从 \(last\) 开始对 \(\mathbf{link}\) 进行遍历,若当前结点 \(v\) 没有 \(v→cur\) 的边,创建一条 \(v→cur\) 的边并标记为 \(\mathbf{ch}\)

  4. 若遍历到了 \(t_0\) 则让 \(\mathbf{link(cur)}=0\) , \(last=cur\) ,回到第一步

  5. 如果当前结点 \(v\) 已经有了标记字符 \(\mathbf{ch}\) 的出边则停止遍历,并把这个结点标记为 \(p\) ,标记 \(p\) 沿着标记字符 \(\mathbf{ch}\) 的出边到达的点为 \(q\) 。

  6. 如果 \(\mathbf{len(p)+1=len(q)}\) ,让 \(\mathbf{link(cur)}=q ,last=cur\) ,回到第一步。

  7. 复制状态 \(q\) 到一个新的状态 \(\mathbf E\) 里(包括 \(\mathbf {link(q)}\) 以及所有 \(q\) 在 \(\mathbf {DAG}\) 上的出边),将 \(\mathbf {len(E)}\) 赋值为 \(\mathbf{len(p)}+1\) 。

    复制之后,再赋值 \(\mathbf{link(q)}=\mathbf E,\mathbf{link(cur)}=\mathbf E\)

    然后从 \(p\) 遍历后缀链接,设当前遍历到的点为 \(v\) ,若 \(v\) 有标记为 \(\mathbf{ch}\) 的出边 \(v→q\) ,则重定向这条边为 \(v→\mathbf E\)

    若 \(v\) 没有标记为 \(c\) 的出边或者 \(v\) 的标记为 \(c\) 的出边所到达的点不是 \(q\) ,停止遍历,\(last=cur\) ,回到第一步

我们一步一步的来看这个算法

  • 找到 \(last\) 来为后面的更新做准备

  • 加入 \(\mathbf{ch}\) 后,我们会形成一个新的等价类(因为 \(\mathbf{endpos}\) 包含了新字符 \(\mathbf{ch}\) 的位置),我们定义这个新的等价类为 \(\mathbf{cur}\)

    根据对 \(\mathbf{last}\) 的定义,我们可以发现 \(\mathbf{last}\) 内最长的字符串一定是 \(S\),所以 \(|S|=\mathbf{len(last)}\)

    我们知道,新加入的字符是 \(\mathbf{ch}\) ,所以新串是 \(S+\mathbf{ch}\),我们需要链接一条从 \(S\) 到 \(cur\) 的边,标记为 \(\mathbf{ch}\) 表示可以从 \(S\) 转移到 \(S+ \mathbf{ch}\)

    那么等价类 \(cur\) 内的最长字符串一定是 \(S+\mathbf{ch}\),长度显然为 \(\mathbf{len(last)}+1\)

  • 遍历 \(\mathbf{link}\) 并尝试加入关于 \(cur\) 的转移,我们知道 \(\mathbf{SAM}\) 是记录的所有后缀,我们只要在后面加入一个 \(\mathbf{ch}\)

    我们知道,从 \(last\) 开始跳 \(\mathbf{link}\) 可以跳到所有后缀,只要依次在这些等价类内向 \(cur\) 试图加入标记为 \(\mathbf{ch}\) 的转移即可

    然而我们只能添加与原有转移不冲突的转移。因此我们只要找到已存在的 \(\mathbf{ch}\) 的转移,我们就必须停止

    下面的图片是对于字符串 \(S=abcba\) 加入一个新的字符 \(d\) 后的结果

    image

    我们发现当从 \(\mathbf{last}\) 一直跳 \(\mathbf{link}\) 跳到了 \(t_0\) 节点,那么证明 \(\mathbf{SAM}\) 内没有出现过 \(\mathbf{ch}\) 节点

  • 我们到达了虚拟状态 \(-1\) ,这意味着我们为所有 \(S\) 的后缀添加了 \(\mathbf{ch}\) 的转移。这也意味着,字符 \(\mathbf{ch}\) 从未在字符串 \(S\) 中出现过。

    因此 \(cur\) 的后缀链接为状态 \(0\)

  • 第二种情况,我们找到了 \((p,q)\) 的状态转移,说明我们正在试图添加一个已经存在的 \(x+\mathbf{ch}\) (\(x\)为当前这个节点代表的 \(S\) 的后缀)

    我们似乎不应该在这里加入一个标记为 \(\mathbf{ch}\) 的转移,所以我们应该把 \(\mathbf{link(cur)}\) 连到一个 \(\mathbf{len}\) 为 \(\mathbf{len(p)+1}\) 的状态上

  • 如果 \(\mathbf{len}(q)=\mathbf{len}(p)+1\),也就是说转移 \((p,q)\) 是连续的

    我们只需要让 \(\mathbf{link(cur)}\) 连到 \(q\) 即可

  • 如果 \(\mathbf{len}(q) > \mathbf{len}(p)+1\),也就是转移 \((p,q)\) 并非连续

    那么这意味着状态 \(q\) 不只对应于长度为 \(\mathbf{len}(p)+1\) 的后缀 \(S+\mathbf{ch}\) ,还对应于 \(s\) 的更长的子串

    我们就被迫只能把 \(q\) 一分为二了,让第一个状态 \(\mathbf{E}\) 的 \(\mathbf{len}\) 为 \(\mathbf{len(p)}+1\)

    首先我们对于 \(q\) 复制一个状态 \(\mathbf{E}\),让 \(\mathbf{len(E)=len(p)+1}\),然后把 \(q\) 的所有转移复制到 \(\mathbf{E}\) 上

    同时,我们把 \(\mathbf{link(E)}\) 的目标也设为 \(\mathbf{link(q)}\) 的目标,并且让 \(\mathbf{link(q)}\) 的目标设定为 \(\mathbf{E}\)

    接下来我们重定向一些边(因为分开之后我们必须要区分清哪些入边构成了被分出去的 \(\mathbf{E}\),哪些构成了还剩下在 \(q\) 中的串),然后继续遍历 \(\mathbf{link}\) 并且分类讨论

    • 找到了一个结点 \(v\) 拥有一条标记 \(\mathbf{ch}\) 的出边指向 \(q\)

      说明 \(v\) 中的串加上 \(\mathbf{ch}\) 构成了 \(\mathbf{E}\) 中的串,我们要把这条边重定向到 \(\mathbf{E}\) 。

    • 找到了一个结点 \(v\) 拥有一条标记 \(\mathbf{ch}\) 的出边,但指向结点不是 \(q\)

      说明 \(v\) 中的串加上 \(\mathbf{ch}\) 构成了一个不在 \(\mathbf{E}\) 集合中的 \(\mathbf{E}\) 内最长串的后缀(\(\mathbf{E}\) 在 \(\mathbf{parent}\) 树上的某一级祖先中的一个串)。

      因为 \(v\) 中的串加上 \(\mathbf{c}\) 无法构成 \(\mathbf{E}\) 中的串,则 \(\mathbf{v}\) 的后缀加上 \(\mathbf{ch}\) 显然也无法构成 \(\mathbf{E}\) 中的一个串。

      也就是说,我们已经把所有要重定向的边完成重定向了,停止遍历即可。

关于 \(\mathbf{SAM}\) 线性复杂度的证明

\(\mathbf{SAM}\) 的复杂度是线性的必要前提是 \(\sum\) 为常数

在使用 map 的情况下时间复杂度为 \(\mathcal O(n \log |\sum|)\),空间复杂度为 \(\mathcal O(n)\)

在不使用 map 的情况下时间复杂度 \(\mathcal O(n)\) , 空间复杂度为 \(\mathcal O(n |\sum|)\)

警惕 SAM 题目常见卡 unordered_map 的坏人 \(\mathbf{QAQ}\)

我们认为字符集的大小为常数,即每次对一个字符搜索转移、添加转移、查找下一个转移的时间复杂度都为 \(O(1)\)

在算法中有三处不是明显线性的,我们一一来分析

  • 遍历所有状态 \(\mathbf{last}\) 的后缀链接,添加字符 \(\mathbf{ch}\) 的转移。

    对于后缀自动机大小,很明显转移数和状态数是线性的,所以这里一定是线性的

  • 当状态 \(q\) 被复制到一个新的状态 \(\mathbf{E}\) 时复制转移的过程

    同上一条,后缀自动机的转移数和状态数很明显是线性的,所以是线性的

  • 第三处是修改指向 \(q\) 的转移,将它们重定向到 \(\mathbf{E}\) 的过程。

    结论: \(\mathbf{longest}(\mathbf{link}(\mathbf{link}(\mathbf{last}))\) 的位置单调递增,所以这个循环最多不会执行超过 \(n\) 次迭代

    证明:

    • 将最初指向 \(q\) 的转移重定向到 \(\mathbf{E}\),记 \(v=\mathbf{longest}(p)\) ,这是一个字符串 \(s\) 的后缀,每次迭代长度都递减(字符串 \(s\) 的位置每次迭代都单调上升)。

    • 这种情况下,如果在循环的第一次迭代之前,相对应的字符串 \(v\) 在距离 \(\mathbf{last}\) 的深度为 \(k (k\ge 2)\) 的位置上(深度记为后缀链接的数量)

    • 那么在最后一次迭代后,字符串 \(v+\mathbf{ch}\) 将会成为路径上第二个从 \(\mathbf{cur}\) 出发的后缀链接(它会成为新的 \(\mathbf{last}\) 的值)

    • 所以 \(\mathbf{longest}(\mathbf{link}(\mathbf{link}(\mathbf{last}))\) 的位置单调递增

实现

下面是基于 map 实现的 SAM,复杂度为 \(O(|S| \log |\sum|)\)

SAM 跑的不应为字符串即为数字时改变 valueType 即可

点击查看代码
#include<bits/stdc++.h>
typedef char valueType;

namespace Suffix_AutoMaton{
#define for_(a,b,ch) for(int a=b;a<=ch;a++)
#define _for(a,b,ch) for(int a=b;a>=ch;a--)

    constexpr int MaxLen=1e5+5;

    class SAM{
     public:
        int len, Link;
        std::map<valueType,int> Next;
    }sam[MaxLen<<1];

    int Size,Last;

    inline void Init() {
        sam[0].len=0;
        sam[0].Link=-1;
        Size++;Last=0;
    }

    inline void Insert(valueType ch) {
        int cur=Size++,p=Last;
        sam[cur].len=sam[Last].len+1;
        while((p!=-1)&&(
            !sam[p].Next.count(ch))){
            sam[p].Next[ch]=cur;
            p=sam[p].Link;
        }
        if(p==-1) 
            sam[cur].Link=0;
        else {
            int q=sam[p].Next[ch];
            if(sam[p].len+1==sam[q].len)
                sam[cur].Link=q;
            else{
                int E=Size++;
                sam[E].len=sam[p].len+1;
                sam[E].Next=sam[q].Next;
                sam[E].Link=sam[q].Link;
                while(p!=-1&&sam[p].Next[ch]==q){
                    sam[p].Next[ch]=E;
                    p=sam[p].Link;
                }
                sam[q].Link=sam[cur].Link=E;
            }
        }
    }

#undef for_
#undef _for
}using namespace Suffix_AutoMaton;

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    
}

性质

  • 对于字符串 \(S\) ,它的 \(\mathbf{SAM}\) 中的状态数 不会超过 \(2|S|-1\)

    证明:

    • 算法本身就可以证明,首先一开始我们会自带状态,然后第一轮和第二轮最多只会创建 \(1\) 个状态

      后面的每轮最多只会创建 \(2\) 个状态,所以不会超过 \(2|S|-1\)

  • 对于字符串 \(S\) ,它的 \(\mathbf{SAM}\) 中的转移数 不会超过 \(3|S|-4\)

  • 分配结束标记

    我们知道,\(\mathbf{SAM}\) 是一个能接收所有后缀的最小的 \(\mathbf{DFA}\),因此我们要分配结束标记

    先构建完整颗 \(\mathbf{SAM}\),这样找到构建完毕后的 \(\mathbf{last}\),然后从 \(\mathbf{last}\) 往根节点跳,路上的所有节点全部打一个结束标记就行了

应用

详见【学习笔记】 - 字符串基础 : 后缀自动机(进阶篇)

例题

详见【学习笔记】 - 字符串基础 : 后缀自动机(进阶篇)

标签:ch,mathbf,后缀,text,基础,link,endpos,自动机
From: https://www.cnblogs.com/Vsinger-LuoTianYi/p/18136248

相关文章

  • python基础之-sys模块、os模块基本介绍(未完成)
    背景介绍在自动化脚本中,经常会用到类似:sys.argv[1]和os.getenv("id")两种方式进行传参,为了便于区分,鉴于自己的理解进行一定记录,后续将继续补充。基本介绍一、sys模块它的很多属性描述程序的执行环境,是python的基础模块。*sys.argv:实现从程序外部向程序传递参数。*sys.a......
  • 数据结构基础第2讲
    数据结构基础第2讲线性表\(\bigstar\bigstar\bigstar\bigstar\bigstar\)本讲知识结构考点一:基本定义和逻辑线性表具有相同特性的数据元素的有限序列考点二:线性表的还是顺序结构\(\bigstar\bigstar\bigstar\bigstar\)存储要点:将线性表中的元素从前往后依次存入一个......
  • 【计算几何】牛客专题第二章 二维基础
    元素的表示点1.复数类·complex<int/duble>·特点:慢,自带各种运算,不怎么用2.pair·自带排序·自由度不高·基本不在几何题目中使用3.结构体(推荐,常用)自由度高,成员函数,重载运算符structPoint{ doublex,y;};向量(直接用Point)向量点积与几何意义及应用\vec{......
  • 3.Java基础学习
    Java基础注释单行注释多行注释文档注释publicclassHelloworld{publicstaticvoidmain(String[]args){//单行注释////输出一个HelloworldSystem.out.println("Helloworld");/*多行注释多行注释......
  • Web前端基础
    HTML&CSS基础HTML:结构(页面元素和内容)css:表现(网页元素的外观和位置等页面样式)行为:JavaScript:行为(网页模型定义与页面交互)排版标签排版标签标题标签:h系列标签重要程度依次递减特点:独占一行、h1-h6文字逐渐减小段落标签:p特点:段落之间存在间隙、独占一行文本格式化标签场景......
  • [02] JS-基础语法(一)
    1.几个概念本文我们讲解一下JS中的几个简单的概念,包括标识符、关键字、保留字、大小写和字面量。这些基本概念虽然不能直接提升我们的编程能力,但它们是JS的基本组成元素。1.1标识符所谓标识符(Identifier),就是名字。JavaScript中的标识符包括变量名、函数名、参数名、属性......
  • Flask基础
    一、简介1、框架介绍Flask是一个基于Python并且依赖于Jinja2模板引擎和WerkzeugWSGI服务的一个微型框架WSGI:WebServerGatewayInterface(WEB服务网关接口),定义了使用python编写的webapp与webserver之间接口格式其他类型框架:Django:比较“重”的框架,同时也是最出名的P......
  • 栈4-后缀表达式
    栈4-后缀表达式中缀转后缀数字:直接输出左括号: 进栈运算符号:与栈顶符号进行优先级比较栈顶若是左括号,优先级最低栈顶符号优先级低: 此符号进栈栈顶符号优先级不低,弹出栈顶符号后进栈右括号:将栈顶符号弹出并输出,知道匹配到左括号遍历结束:弹出并输出所......
  • [03] JS-基础语法(二)
    1.判断、循环1.1if-elseif语句ifelse语句ifelseifelse语句e.g.编写一个程序,获取一个用户输入的整数,然后显示这个数是奇数还是偶数。//编写一个程序,获取一个用户输入的整数//letnum=+prompt("请输入一个整数")letnum=parseInt(prompt("请输入一个整数"......
  • 栈5-后缀表达式求解
    栈5-后缀表达式的求解求解过程831-5*+数字:进栈[1,3,8]符号:-从栈中弹出右操作数-1从栈中弹出左操作数3-1根据符号进行运算2将运算结果压入栈中[2,8]遍历结束,栈中唯一的数字作为计算结果定义栈结构typedefstructMYNUM{LinkNodenode;int......