跳转至

广义后缀自动机 exSAM

本文转载（或修改）自 OI-Wiki

前置知识：后缀自动机 SAM

引入

P6139 【模板】广义后缀自动机（广义 SAM）

给定 \(n\) 个由小写字母组成的字符串 \(s_1,s_2\ldots s_n\)，求本质不同的子串个数。（不包含空串）

进一步，设 \(Q\) 为能接受 \(s_1,s_2,\dots,s_n\) 的所有后缀的最小 DFA，请你输出 \(Q\) 的点数。（如果你无法理解这句话，可以认为就是输出 \(s_1,s_2,\dots,s_n\) 建成的“广义后缀自动机”的点数）。

数据范围： \(1\le n\le 4\cdot 10^5\)， \(1\le \sum{|s_i|}\le 10^6\)。

起源

广义后缀自动机是由刘研绎在其 2015 国家队论文《后缀自动机在字典树上的拓展》上提出的一种结构，即将后缀自动机直接建立在字典树上。

大部分可以用后缀自动机处理的字符串的问题均可扩展到 Trie 树上。——刘研绎

约定

字符串个数为 \(k\) 个，即 \(S_1, S_2, S_3 \dots S_k\)

约定字典树和广义后缀自动机的根节点为 \(1\) 号节点

概述

后缀自动机 (suffix automaton, SAM) 是用于处理单个字符串的子串问题的强力工具。

而广义后缀自动机 (General Suffix Automaton) 则是将后缀自动机整合到字典树中来解决对于多个字符串的子串问题

常见的伪广义后缀自动机

  1. 通过用特殊符号将多个串直接连接后，再建立 SAM
  2. 对每个串，重复在同一个 SAM 上进行建立，每次建立前，将 lst 指针置为根节点 \(1\)

一般情况下，这两种方法的时间复杂度与 exSAM 的最坏时间复杂度相同，但如果题目给的是 Trie 的话效率差距就很大了。

离线构建广义后缀自动机

根据原论文的描述，应当在多个字符串上先建立字典树，然后在字典树的基础上建立广义后缀自动机。

后缀自动机的建立

如果我们把这样一棵树直接认为是一个后缀自动机，则我们可以得到如下结论

  • 对于节点 i，其 len[i] 和它在字典树中的深度相同
  • 如果我们对字典树进行拓扑排序，我们可以得到一串根据 len 不递减的序列。BFS 的结果相同

而后缀自动机在建立的过程中，可以视为不断的插入 len 严格递增的值，且差值为 \(1\)。所以我们可以将对字典树进行拓扑排序后的结果做为一个队列，然后按照这个队列的顺序不断地插入到后缀自动机中。

由于在普通后缀自动机上，其前一个节点的 len 值为固定值，即为 lst 节点的 len。但是在广义后缀自动机中，插入的队列是一个不严格递增的数列。所以对于每一个值，对于它的 lst 应该是已知而且固定的，在字典树上，即为其父亲节点。

由于在字典树中，已经建立了一个近似的后缀自动机，所以只需要对整个字典树的结构进行一定的处理即可转化为广义后缀自动机。我们可以按照前面提出的队列顺序来对整个字典树上的每一个节点进行更新操作。最终我们可以得到广义后缀自动机。

对于每个点的更新操作，我们可以稍微修改一下 SAM 中的插入操作来得到。

对于整个插入的过程，需要注意的是，由于插入是按照 len 不递减的顺序插入，在进行 nq 后的数据复制过程中，不可以复制其 len 小于当前 len 的数据。

过程

根据上述的逻辑，可以将整个构建过程描述为如下操作

  1. 将所有字符串插入到字典树中
  2. 从字典树的根节点开始进行 BFS，记录下顺序以及每个节点的父亲节点
  3. 将得到的 BFS 序列按照顺序，对每个节点在原字典树上进行构建，注意不能将 len 小于当前 len 的数据进行操作

对操作次数为线性的证明

由于仅处理 BFS 得到的序列，可以保证字典树上所有节点仅经过一次。

对于最坏情况，考虑字典树本身节点个数最多的情况，即任意两个字符串没有相同的前缀，则节点个数为 \(\sum_{i=1}^{k}|S_i|\)，即所有的字符串长度之和。

而在后缀自动机的更新操作的复杂度已经在 后缀自动机 中证明

所以可以证明其最坏复杂度为线性

实现

对插入函数进行少量必要的修改即可得到所需要的函数

对于模板题，可以根据后缀自动机的性质得到，以点 \(i\) 为结束节点的子串个数等于 \(len[i] - len[fa[i]]\)

所以可以遍历所有的节点求和得到

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 2e6 + 10;
int n;
ll ans;
string s;
struct SAM
{
    int len[MAXN], son[MAXN][26], fa[MAXN], tot;
    int newnode(int l) { return len[++tot] = l, tot; }
    SAM() : len{}, fa{}, son{}, tot(0) { newnode(0); }
    int insertSAM(int c, int f)
    {
        int np = son[f][c];
        if (len[np]) return np;
        len[np] = len[f] + 1;
        int p = fa[f];
        while (p && !son[p][c]) son[p][c] = np, p = fa[p];
        if (!p) return fa[np] = 1, np;
        int q = son[p][c];
        if (len[q] == len[p] + 1) return fa[np] = q, np;
        int nq = newnode(len[p] + 1);
        for (int i = 0; i < 26; i++)
            if (len[son[q][i]]) son[nq][i] = son[q][i];
        fa[nq] = fa[q], fa[q] = fa[np] = nq;
        while (p && son[p][c] == q) son[p][c] = nq, p = fa[p];
        return np;
    }
    void insertTrie(string s)
    {
        int u = 1;
        for (char c : s)
        {
            int &v = son[u][c - 'a'];
            if (!v) v = newnode(0);
            u = v;
        }
    }
    void buildSAM()
    {
        queue<pii> q;
        for (int i = 0; i < 26; i++)
            if (son[1][i]) q.push({i, 1});
        while (!q.empty())
        {
            auto [c, f] = q.front();
            q.pop();
            int u = insertSAM(c, f);
            for (int i = 0; i < 26; i++)
                if (son[u][i]) q.push({i, u});
        }
    }
} sam;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    while (n--) cin >> s, sam.insertTrie(s);
    sam.buildSAM();
    for (int i = 2; i <= sam.tot; i++) ans += sam.len[i] - sam.len[sam.fa[i]];
    cout << ans << endl
         << sam.tot;
    return 0;
}
  • 由于整个 BFS 的过程得到的顺序，其父节点始终在变化，所以并不需要保存 lst 指针。
  • 插入操作中，int np = son[lst][c]; 与正常后缀自动机的 int np = newnode(len[lst] + 1); 有差异，因为我们插入的节点已经在树型结构中完成了，所以只需要直接获取即可
  • 在 nq 后的 son 拷贝中，有这样的判断 if(len[son[q][i]]) son[nq][i] = son[q][i]; 这与正常的后缀自动机的直接赋值 son[nq][i] = son[q][i]; 有一定差异，此次是为了避免更新了 len 大于当前节点的值。

性质

  1. 广义后缀自动机与后缀自动机的结构一致，在后缀自动机上的性质绝大部分均可在广义后缀自动机上生效（后缀自动机的性质）
  2. 当广义后缀自动机建立后，通常字典树结构将会被破坏，即通常不可以用广义后缀自动机来解决字典树问题。当然也可以选择准备双倍的空间，将后缀自动机建立在另外一个空间上。

在线构建广义后缀自动机

不同于前面的 Trie 树构建，有没有在线的做法呢？

事实上是有的，这依旧依赖于对 insert() 的小修改。

和上面一样，lst 不记录在 exSAM 中而是由 insert() 返回，每次在上次的基础上新增节点。

对每个字符串，我们都从 lst = 1 开始构建 exSAM，但是和上面的伪广义后缀自动机不同，我们对 \(son_{lst, c}\) 是否已存在分类讨论：

  • 如果还不存在，那么按照正常的 SAM 执行即可。
  • 否则，我们令 \(p \leftarrow lst, np \leftarrow son_{lst, c}\) 并检查是否有 \(len_{np} = len_{p} + 1\) ：
    • 如果是，那么 \(np\) 就是我们想新建的点，直接返回即可。
    • 否则我们要做类似 SAM 中分裂的事情，我们令 \(nq \leftarrow clone(np)\)，令 \(len_{nq} \leftarrow len_{np} + 1\)，并一样的跳后缀链接去一路修改所有到 \(np\) 的转移，不用的是，这里的 \(nq\) 才是真正代表我们新来的字符的节点，因此应当返回 \(nq\)。

模板题的实现如下：

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 2e6 + 10;
int n;
ll ans;
string s;
struct SAM
{
    array<int, 26> son[MAXN];
    int len[MAXN], fa[MAXN], tot;
    int newnode(const int l) { return len[++tot] = l, tot; }
    SAM() : len{}, fa{}, tot(0) { newnode(0); }
    int insert(const int c, const int lst)
    {
        int p = lst, np = son[lst][c];
        if (np) // 如果这个转移已经有了，检查是否符合要求
        {
            if (len[np] == len[p] + 1) // 符合则直接返回
                return np;
            int nq = newnode(len[p] + 1); // 否则分裂，新建节点
            son[nq] = son[np], fa[nq] = fa[np], fa[np] = nq;
            while (p && son[p][c] == np) son[p][c] = nq, p = fa[p];
            return nq; // 这里需要注意的是，新建的这个节点才代表我们新来的字符，因此返回 nq 并非 np
        }
        // 如果这个转移还没有，那就是正常的 SAM
        np = newnode(len[p] + 1);
        while (p && !son[p][c]) son[p][c] = np, p = fa[p];
        if (!p) return fa[np] = 1, np;
        int q = son[p][c];
        if (len[q] == len[p] + 1) return fa[np] = q, np;
        int nq = newnode(len[p] + 1);
        son[nq] = son[q], fa[nq] = fa[q], fa[q] = fa[np] = nq;
        while (p && son[p][c] == q) son[p][c] = nq, p = fa[p];
        return np;
    }
    void insertString(const string s)
    {
        int lst = 1;
        for (char c : s) lst = insert(c - 'a', lst); // 以上一个结点为基础建树
    }
} sam;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    while (n--) cin >> s, sam.insertString(s);
    for (int i = 2; i <= sam.tot; i++) ans += sam.len[i] - sam.len[sam.fa[i]];
    cout << ans << endl
         << sam.tot;
    return 0;
}

有意思的是，在线构建 exSAM 的常数比离线构建还小！