【算法】后缀自动机的那些事

请注意,本文编写于 256 天前,最后修改于 86 天前,其中某些信息可能已经过时。

概念

对于一个字符串 $S$ ,它对应的后缀自动机是一个最小的确定有限状态自动机(DFA),接受且只接受 $S$ 的后缀
在 SAM 上,对于 $S$ 的子串,最终会达到一个合法状态,否则将会“无路可走”

有限状态自动机(DFA)可以用一个五元组 <字符集,状态集,转移函数,起始状态集,结束状态集> 来描述

States 状态

对于给定的字符集 $S$ ,如何确定其状态?
引入 子串结束位置 $endpos$ ,描述本质相同子串结束位置的集合
如果两个子串 $endpos$ 相同,则归为一类
最终由 $endpos$ 的等价类就成为了 SAM 的状态集合

例如 $S = “aabbabd”$ ,其 $endpos$ 状态为

状态子串$endpos$
S空串{0,1,2,3,4,5,6}
1a{1,2,5}
2aa{2}
3aab{3}
4aabb,abb,bb{4}
5b{3,4,6}
6aabba,abba,bba,ba{5}
7aabbab,abbab,bbab,bab{6}
8ab{3,6}
9aabbabd,abbabd,bbabd,babd,abd,bd,d{7}

观察发现,对于 $S$ 的两个子串 $s1,s2$ ,不妨设 $|s1| \leq |s2|$

  • 如果 $s1$ 为 $s2$ 的后缀,当且仅当 $endpos(s1) \supseteq endpos(s2)$
  • 如果 $s1$ 不为 $s2$ 的后缀,当且仅当 $endpos(s1) \cap endpos(s2) = \emptyset$

证明一:
若 $s1$ 为 $s2$ 后缀,每个 $s2$ 出现时,必定出现 $s1$ ,并且结束位置相同,同时, $s1$ 出现时不一定出现 $s2$ ,所以 $endpos(s1) \supseteq endpos(s2)$
反之,若 $endpos(s1) \supseteq endpos(s2)$ ,对于每一个出现的 $s2$ 必然有 $s1$ 与其同时结束,所以 $s1$ 为 $s2$ 后缀

证明二:
考虑反证法,若 $endpos(s1) \cap endpos(s2) \neq \emptyset$ ,则 $\exists e1 \in endpos(s1) , \exists e2 \in endpos(2) , e1 = e2$
那么在 $e1$ 位置,$s1 , s2$ 同时结束,所以 $s1$ 为 $s2$ 后缀


考虑到对于每一个状态 $S$ ,其子串有相同的 $endpos$ ,所以它们互为后缀

设 $str(S)$ 为 $S$ 状态包含的所有子串, $long(S)$ 为 $S$ 状态包含的最长子串, $short(S)$ 为 $S$ 状态包含的最短子串

  • 当且仅当 $s$ 为 $long(S)$ 的后缀,$short(S)$ 为 $s$ 的后缀, $s \in str(S)$

证明:
若 $s$ 为 $long(S)$ 的后缀,$short(S)$ 为 $s$ 的后缀, $|short(S)| \leq |s| \leq |long(S)|$ ,所以 $endpos(short(S)) \supseteq endpos(s) \supseteq endpos(long(S))$ ,即 $endpos(short(S)) = endpos(s) = endpos(long(S))$ ,所以 $s \in str(S)$
反之,若 $s \in str(S)$ , $|short(S)| \leq |s| \leq |long(S)|$ , 则显然 $endpos(short(S)) \supseteq endpos(s) \supseteq endpos(long(S))$ ,所以 $s$ 为 $long(S)$ 的后缀,$short(S)$ 为 $s$ 的后缀

所以说 $str(S)$ 包含了 $long(S)$ 的一系列 连续 后缀

上文中提到 $str(S)$ 包含了 $long(S)$ 的一系列 连续 后缀,而不是 所有 后缀,是因为这连续的后缀会在某个位置“断掉”
比如说 状态 7 中, $long(7) = “aabbab”$ , $str(7) = “aabbab”,“abbab”,“bbab”,“bab”$
按照惯例,下一个串应该是 $“ab”$ ,并且 $“ab”$ 显然在结束位置 6 出现过
但是因为 $“ab”$ 在结束位置 3 出现过,所以 $endpos(“ab”) = {3,6}$ , 结束位置比 $str(7)$ 的所有子串要多,于是被分配到了新的状态 8

同理,当考虑 $“ab”$ 的后缀 $“b”$ 时也会遇到这样的情况, $endpos(“b”) = {3,4,6}$ ,属于状态 5 ,接下来是空串 $endpos(“”) = {0,1,2,3,4,5,6}$ ,属于起始状态 $S$

于是可以发现一条状态序列 $7 -> 8 -> 5 -> S$ ,即 Suffix Link 后缀链接
将状态 $S$ 的 Suffix Link 记为 $slink(S)$

因为后缀连接是严格按照长度递减的,所以其形成了一棵以 $S$ 为根的树,维护了包含关系

Transition Function 转移函数

对于一个状态 $S$ ,将其可能遇到的下一个字符集记为 $nxt(S)$ ,显然有 $nxt(S) = \{s[i + 1] | i \in endpos(S)\}$

对于状态 $S$ 的 $str(S)$ ,在后面加上一个字符 $c \in nxt(S)$ 其新子串必定仍然属于同一个状态

所以我们对于一个状态 $S$ 和字符 $c \in nxt(S)$ ,定义转移函数 $trans(S , c) = x | str(S) + c \in str(x)$

后面我们可以通过转移函数来进行匹配

建图

显然,对于状态 $S$ 将所有数据保存下来是不可能的,仅仅储存 $|long(S)| , |short(S)| , trans(S) , slink(S)$

假设已经够造好了 $s[1 \cdots i]$ 的 SAM ,这时我们需要添加字符 $s[i + 1]$ ,于是新增了 $s[1 \cdots i + 1] , s[2 \cdots i + 1] , \cdots , s[i + 1]$ 共 $i + 1$ 个子串进行识别。考虑到这些子串是由 $s[1 \cdots i] , s[2 \cdots i] , \cdots , s[i] ,$空串 转移而来,所以还要为它们增加对应的转移

  • 首先新建一个状态 $np$
  • 从从结束状态开始通过 $slink$ 往前跳

    • 当当前状态都没有向 $s[i + 1]$ 的转移时,直接将其转移到状态 $np$
    • 当前状态 $x$ 有向 $s[i + 1]$ 的转移,指向 $y$ ,并且 $l[x] + 1 = l[y]$ 时,直接将 $slink[np]$ 设为 $y$ ,结束
    • 当前状态 $x$ 有向 $s[i + 1]$ 的转移,指向 $y$ ,并且 $l[x] + 1 \neq l[y]$ 时,新建一个节点 $ny$ 保存 $y$ 状态中所有长度小于等于 $l[x] + 1$ 的部分(其实就是除了长度改变完全拷贝) , $l[ny] = l[x] + 1$ ,将原来所有指向 $y$ 状态的状态全都指向 $ny$ ,同时将 $slink[y]$ 和 $slink[nq]$ 连向 $ny$(维护最短长度),结束
    • 若没有结束, $slink[np]$ 连向 $S$ 结束

为什么要做这么复杂的拷贝操作呢?

我们已经得知 $x$ 状态必然是 $last$ 状态的一个后缀,这次增加的串仅仅能保证前 $l[x]$ 位相同,后 $1$ 位相同,也就是说仅能增加长度为 $[1,l[x]+1]$ 的一系列子串的 $endpos$,所以说对于更长的串,他们的 $endpos$ 集合已经不同了,必须分开

使用方法

存在性查询

  • 给定文本串 $s$ 每次给定字符串 $t$ ,问 $t$ 是否是 $s$ 的子串
  • 预处理 $O(|s|)$ ,询问 $O(|t|)$

首先建立后缀自动机

现在回答单次询问,对于字符串 $t$ 每一位,通过 $trans$ 进行转移
如果当前没有能够转移的状态,答案为 $No$
如果成功处理了整个串 $t$ ,答案为 $Yes$

该算法实际上找到的是 $t$ 在 $s$ 中出现的最长前缀

不同的子串数量

  • 给定文本串 $s$ ,求其本质不同的子串数
  • $O(|s|)$

首先建立后缀自动机

在后缀自动机中, $s$ 的任意子串都对应着自动机中的一条路径,答案为从根节点开始,自动机中的不同路径数
显然自动机是一个有向无环图,所以考虑用动态规划计算不同的路径数量
设 $d[x]$ 为状态 $x$ 开始的不同路径数量,则有
$$d[x] = 1 + \sum_{y \in trans[x][0 \cdots 25]} d[y]$$

答案为 $d[rt] - 1$

当然,答案也可以是 $\sum_{x=1}^{node} |l[x]-l[slink[x]]|$

不同子串总长

显然通过上一题可以看出转移

$$ d[x] = 1 + \sum_{y \in trans[x][0 \cdots 25]} d[y]\\ ans[x] = \sum_{y \in trans[x][0 \cdots 25]} d[y] + ans[y] $$

字典序第 k 小

显然通过上两题可以看出转移

先将本质子串算出来,然后从根开始找到答案区间,如果没有输出 -1

最小循环移位

  • 给定字符串 $s$ ,找到其循环同构的字典序最小字符串
  • $O(|s|)$

将字符串 $s + s$ 建立后缀自动机,即包含了其所有循环同构串,我们贪心的从根节点开始跑即可

出现次数查询

  • 给定文本串 $s$ 每次给定字符串 $t$ ,问 $t$ 在 $s$ 中出现了几次
  • 预处理 $O(|s|)$ ,询问 $O(|t|)$

发现当插入节点(建图)时,若出现情况 $2$ 时,即串多出现了一次,所以对于非复制状态,令 $siz[x] = 1$ ,跑拓扑时转移

$$siz[x] = siz[x] + \sum_{y \in trans[x][0 \cdots 25]} siz[y]$$

然后每个串进行匹配,匹配结束状态的 $siz$ 即为该串出现次数

首次出现位置查询

  • 给定文本串 $s$ 每次给定字符串 $t$ ,问 $t$ 在 $s$ 中第一次出现在哪
  • 预处理 $O(|s|)$ ,询问 $O(|t|)$

在建立后缀自动机时对于每一个状态保存一个 $firstpos$
当我们确立新的状态 $x$ 时,只需要使得 $firstpos[x] = l[x]$
拷贝节点时同时拷贝 $firstpos$ 因为后面插入的新 $pos$ 一定比 $firstpos$ 大

然后每个串进行匹配,输出 $firstpos[x] - |t|$


其实后缀自动机还有很多用法,在这里不一一细讲

最后放上自己的板子

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
struct edge {int t , n;}e[N << 1];
int head[N << 1] , tot;
void addedge(int u , int v) {
    ++ tot;
    e[tot].t = v;
    e[tot].n = head[u];
    head[u] = tot;
};
char str[N];
struct SAM {
    int last , cnt;
    int l[N << 1] , trans[N << 1][27] , slink[N << 1] , siz[N << 1];
    long long ans;
    void ins(int c) {
        int x = last , nx = ++ cnt; last = nx; l[nx] = l[x] + 1;
        for(; x && ! trans[x][c] ; x = slink[x]) trans[x][c] = nx;
        if(!x) slink[nx] = 1;
        else {
            int y = trans[x][c];
            if(l[x] + 1 == l[y]) slink[nx] = y;
            else {
                int ny = ++ cnt; l[ny] = l[x] + 1;
                memmove(trans[ny] , trans[y] , sizeof(trans[y]));
                slink[ny] = slink[y]; slink[y] = slink[nx] = ny;
                for(; trans[x][c] == y ; x = slink[x]) trans[x][c] = ny;
            }
        }
    }
    void insert(char *s) {
        int n = strlen(s);
        last = cnt = 1;//1 号节点为空
        for(int i = 0 ; i < n ; ++ i) ins(s[i] - 'a');
    }
    void build() {
        for(int i = 2 ; i <= cnt ; ++ i)
            addedge(slink[i] , i);
    }
}sam;
int main() {
    scanf("%s" , str);
    sam.insert(str);
    sam.build();
    return 0;
}
Comments

添加新评论