跳转至

廣義後綴自動機

前置知識

廣義後綴自動機基於下面的知識點

請務必對上述兩個知識點非常熟悉之後，再來閲讀本文，特別是對於 後綴自動機 中的 後綴鏈接 能夠有一定的理解

引入

起源

廣義後綴自動機是由劉研繹在其 2015 國家隊論文《後綴自動機在字典樹上的拓展》上提出的一種結構，即將後綴自動機直接建立在字典樹上。

大部分可以用後綴自動機處理的字符串的問題均可擴展到 Trie 樹上。——劉研繹

約定

參考 字符串約定

字符串個數為 \(k\) 個，即 \(S_1, S_2, S_3 \dots S_k\)

約定字典樹和廣義後綴自動機的根節點為 \(0\) 號節點

概述

後綴自動機 (suffix automaton, SAM) 是用於處理單個字符串的子串問題的強力工具。

而廣義後綴自動機 (General Suffix Automaton) 則是將後綴自動機整合到字典樹中來解決對於多個字符串的子串問題

常見的偽廣義後綴自動機

  1. 通過用特殊符號將多個串直接連接後，再建立 SAM
  2. 對每個串，重複在同一個 SAM 上進行建立，每次建立前，將 last 指針置零

方法 1 和方法 2 的實現方式簡單，而且在面對題目時通常可以達到和廣義後綴自動機一樣的正確性。所以在網絡上很多人會選擇此類寫法，例如在後綴自動機一文中最後一個應用，便使用了方法 1 （原文鏈接）

但是無論方法 1 還是方法 2，其時間複雜度較為危險

構造廣義後綴自動機

根據原論文的描述，應當在多個字符串上先建立字典樹，然後在字典樹的基礎上建立廣義後綴自動機。

字典樹的使用

首先應對多個串創建一棵字典樹，這不是什麼難事，如果你已經掌握了前置知識的前提下，可以很快的建立完畢。這裏為了統一上下文的代碼，給出一個可能的字典樹代碼。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#define MAXN 2000000
#define CHAR_NUM 30

struct Trie {
  int next[MAXN][CHAR_NUM];  // 轉移
  int tot;                   // 節點總數：[0, tot)

  void init() { tot = 1; }

  int insertTrie(int cur, int c) {
    if (next[cur][c]) return next[cur][c];
    return next[cur][c] = tot++;
  }

  void insert(const string &s) {
    int root = 0;
    for (auto ch : s) root = insertTrie(root, ch - 'a');
  }
};

這裏我們得到了一棵依賴於 next 數組建立的一棵字典樹。

後綴自動機的建立

如果我們把這樣一棵樹直接認為是一個後綴自動機，則我們可以得到如下結論

  • 對於節點 i，其 len[i] 和它在字典樹中的深度相同
  • 如果我們對字典樹進行拓撲排序，我們可以得到一串根據 len 不遞減的序列。BFS 的結果相同

而後綴自動機在建立的過程中，可以視為不斷的插入 len 嚴格遞增的值，且差值為 \(1\)。所以我們可以將對字典樹進行拓撲排序後的結果做為一個隊列，然後按照這個隊列的順序不斷地插入到後綴自動機中。

由於在普通後綴自動機上，其前一個節點的 len 值為固定值，即為 last 節點的 len。但是在廣義後綴自動機中，插入的隊列是一個不嚴格遞增的數列。所以對於每一個值，對於它的 last 應該是已知而且固定的，在字典樹上，即為其父親節點。

由於在字典樹中，已經建立了一個近似的後綴自動機，所以只需要對整個字典樹的結構進行一定的處理即可轉化為廣義後綴自動機。我們可以按照前面提出的隊列順序來對整個字典樹上的每一個節點進行更新操作。最終我們可以得到廣義後綴自動機。

對於每個點的更新操作，我們可以稍微修改一下 SAM 中的插入操作來得到。

對於整個插入的過程，需要注意的是，由於插入是按照 len 不遞減的順序插入，在進行 clone 後的數據複製過程中，不可以複製其 len 小於當前 len 的數據。

過程

根據上述的邏輯，可以將整個構建過程描述為如下操作

  1. 將所有字符串插入到字典樹中
  2. 從字典樹的根節點開始進行 BFS，記錄下順序以及每個節點的父親節點
  3. 將得到的 BFS 序列按照順序，對每個節點在原字典樹上進行構建，注意不能將 len 小於當前 len 的數據進行操作

對操作次數為線性的證明

由於僅處理 BFS 得到的序列，可以保證字典樹上所有節點僅經過一次。

對於最壞情況，考慮字典樹本身節點個數最多的情況，即任意兩個字符串沒有相同的前綴，則節點個數為 \(\sum_{i=1}^{k}|S_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
struct GSA {
  int len[MAXN];             // 節點長度
  int link[MAXN];            // 後綴鏈接，link
  int next[MAXN][CHAR_NUM];  // 轉移
  int tot;                   // 節點總數：[0, tot)

  int insertSAM(int last, int c) {
    int cur = next[last][c];
    len[cur] = len[last] + 1;
    int p = link[last];
    while (p != -1) {
      if (!next[p][c])
        next[p][c] = cur;
      else
        break;
      p = link[p];
    }
    if (p == -1) {
      link[cur] = 0;
      return cur;
    }
    int q = next[p][c];
    if (len[p] + 1 == len[q]) {
      link[cur] = q;
      return cur;
    }
    int clone = tot++;
    for (int i = 0; i < CHAR_NUM; ++i)
      next[clone][i] = len[next[q][i]] != 0 ? next[q][i] : 0;
    len[clone] = len[p] + 1;
    while (p != -1 && next[p][c] == q) {
      next[p][c] = clone;
      p = link[p];
    }
    link[clone] = link[q];
    link[cur] = clone;
    link[q] = clone;
    return cur;
  }

  void build() {
    queue<pair<int, int>> q;
    for (int i = 0; i < 26; ++i)
      if (next[0][i]) q.push({i, 0});
    while (!q.empty()) {
      auto item = q.front();
      q.pop();
      auto last = insertSAM(item.second, item.first);
      for (int i = 0; i < 26; ++i)
        if (next[last][i]) q.push({i, last});
    }
  }
}
  • 由於整個 BFS 的過程得到的順序，其父節點始終在變化，所以並不需要保存 last 指針。
  • 插入操作中，int cur = next[last][c]; 與正常後綴自動機的 int cur = tot++; 有差異，因為我們插入的節點已經在樹型結構中完成了，所以只需要直接獲取即可
  • 在 clone 後的數據拷貝中，有這樣的判斷 next[clone][i] = len[next[q][i]] != 0 ? next[q][i] : 0; 這與正常的後綴自動機的直接賦值 next[clone][i] = next[q][i]; 有一定差異，此次是為了避免更新了 len 大於當前節點的值。由於數組中 len 當且僅當這個值被 BFS 遍歷並插入到後綴自動機後才會被賦值

性質

  1. 廣義後綴自動機與後綴自動機的結構一致，在後綴自動機上的性質絕大部分均可在廣義後綴自動機上生效（後綴自動機的性質）
  2. 當廣義後綴自動機建立後，通常字典樹結構將會被破壞，即通常不可以用廣義後綴自動機來解決字典樹問題。當然也可以選擇準備雙倍的空間，將後綴自動機建立在另外一個空間上。

應用

所有字符中不同子串個數

可以根據後綴自動機的性質得到，以點 \(i\) 為結束節點的子串個數等於 \(len[i] - len[link[i]]\)

所以可以遍歷所有的節點求和得到

例題：【模板】廣義後綴自動機（廣義 SAM）

參考代碼 
  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
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000000;  // 双倍字符串长度
const int CHAR_NUM = 30;   // 字符集个数，注意修改下方的 (-'a')

struct exSAM {
  int len[MAXN];             // 节点长度
  int link[MAXN];            // 后缀链接，link
  int next[MAXN][CHAR_NUM];  // 转移
  int tot;                   // 节点总数：[0, tot)

  void init() {  // 初始化函数
    tot = 1;
    link[0] = -1;
  }

  int insertSAM(int last, int c) {  // last 为父 c 为子
    int cur = next[last][c];
    if (len[cur]) return cur;
    len[cur] = len[last] + 1;
    int p = link[last];
    while (p != -1) {
      if (!next[p][c])
        next[p][c] = cur;
      else
        break;
      p = link[p];
    }
    if (p == -1) {
      link[cur] = 0;
      return cur;
    }
    int q = next[p][c];
    if (len[p] + 1 == len[q]) {
      link[cur] = q;
      return cur;
    }
    int clone = tot++;
    for (int i = 0; i < CHAR_NUM; ++i)
      next[clone][i] = len[next[q][i]] != 0 ? next[q][i] : 0;
    len[clone] = len[p] + 1;
    while (p != -1 && next[p][c] == q) {
      next[p][c] = clone;
      p = link[p];
    }
    link[clone] = link[q];
    link[cur] = clone;
    link[q] = clone;
    return cur;
  }

  int insertTrie(int cur, int c) {
    if (next[cur][c]) return next[cur][c];  // 已有该节点 直接返回
    return next[cur][c] = tot++;            // 无该节点 建立节点
  }

  void insert(const string &s) {
    int root = 0;
    for (auto ch : s) root = insertTrie(root, ch - 'a');
  }

  void insert(const char *s, int n) {
    int root = 0;
    for (int i = 0; i < n; ++i)
      root =
          insertTrie(root, s[i] - 'a');  // 一边插入一边更改所插入新节点的父节点
  }

  void build() {
    queue<pair<int, int>> q;
    for (int i = 0; i < 26; ++i)
      if (next[0][i]) q.push({i, 0});
    while (!q.empty()) {  // 广搜遍历
      auto item = q.front();
      q.pop();
      auto last = insertSAM(item.second, item.first);
      for (int i = 0; i < 26; ++i)
        if (next[last][i]) q.push({i, last});
    }
  }
} exSam;

char s[1000100];

int main() {
  int n;
  cin >> n;
  exSam.init();
  for (int i = 0; i < n; ++i) {
    cin >> s;
    int len = strlen(s);
    exSam.insert(s, len);
  }
  exSam.build();
  long long ans = 0;
  for (int i = 1; i < exSam.tot; ++i) {
    ans += exSam.len[i] - exSam.len[exSam.link[i]];
  }
  cout << ans << endl;
}

多個字符串間的最長公共子串

我們需要對每個節點建立一個長度為 \(k\) 的數組 flag（對於本題而言，可以僅為標記數組，若需要求出此子串的個數，則需要改成計數數組）

在字典樹插入字符串時，對所有節點進行計數，保存在當前字符串所在的數組

然後按照 len 遞減的順序遍歷，通過後綴鏈接將當前節點的 flag 與其他節點的合併

遍歷所有的節點，找到一個 len 最大且滿足對於所有的 k，其 flag 的值均為非 \(0\) 的節點，此節點的 \(len\) 即為解

例題：SPOJ Longest Common Substring II

參考代碼 
  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
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000000;  // 双倍字符串长度
const int CHAR_NUM = 30;   // 字符集个数，注意修改下方的 (-'a')
const int NUM = 15;        // 字符串个数

struct exSAM {
  int len[MAXN];             // 节点长度
  int link[MAXN];            // 后缀链接，link
  int next[MAXN][CHAR_NUM];  // 转移
  int tot;                   // 节点总数：[0, tot)
  int lenSorted[MAXN];   // 按照 len 排序后的数组，仅排序 [1, tot)
                         // 部分，最终下标范围 [0, tot - 1)
  int sizeC[MAXN][NUM];  // 表示某个字符串的子串个数
  int curString;         // 字符串实际个数
  /**
   * 计数排序使用的辅助空间数组
   */
  int lc[MAXN];  // 统计个数

  void init() {
    tot = 1;
    link[0] = -1;
  }

  int insertSAM(int last, int c) {
    int cur = next[last][c];
    len[cur] = len[last] + 1;
    int p = link[last];
    while (p != -1) {
      if (!next[p][c])
        next[p][c] = cur;
      else
        break;
      p = link[p];
    }
    if (p == -1) {
      link[cur] = 0;
      return cur;
    }
    int q = next[p][c];
    if (len[p] + 1 == len[q]) {
      link[cur] = q;
      return cur;
    }
    int clone = tot++;
    for (int i = 0; i < CHAR_NUM; ++i)
      next[clone][i] = len[next[q][i]] != 0 ? next[q][i] : 0;
    len[clone] = len[p] + 1;
    while (p != -1 && next[p][c] == q) {
      next[p][c] = clone;
      p = link[p];
    }
    link[clone] = link[q];
    link[cur] = clone;
    link[q] = clone;
    return cur;
  }

  int insertTrie(int cur, int c) {
    if (!next[cur][c]) next[cur][c] = tot++;
    sizeC[next[cur][c]][curString]++;
    return next[cur][c];
  }

  void insert(const string &s) {
    int root = 0;
    for (auto ch : s) root = insertTrie(root, ch - 'a');
    curString++;
  }

  void insert(const char *s, int n) {
    int root = 0;
    for (int i = 0; i < n; ++i) root = insertTrie(root, s[i] - 'a');
    curString++;
  }

  void build() {
    queue<pair<int, int>> q;
    for (int i = 0; i < 26; ++i)
      if (next[0][i]) q.push({i, 0});
    while (!q.empty()) {  // 广搜遍历
      auto item = q.front();
      q.pop();
      auto last = insertSAM(item.second, item.first);
      for (int i = 0; i < 26; ++i)
        if (next[last][i]) q.push({i, last});
    }
  }

  void sortLen() {
    for (int i = 1; i < tot; ++i) lc[i] = 0;
    for (int i = 1; i < tot; ++i) lc[len[i]]++;
    for (int i = 2; i < tot; ++i) lc[i] += lc[i - 1];
    for (int i = 1; i < tot; ++i) lenSorted[--lc[len[i]]] = i;
  }

  void getSizeLen() {
    for (int i = tot - 2; i >= 0; --i)
      for (int j = 0; j < curString; ++j)
        sizeC[link[lenSorted[i]]][j] += sizeC[lenSorted[i]][j];
  }
} exSam;

int main() {
  exSam.init();  // 初始化
  string s;
  while (cin >> s) exSam.insert(s);
  exSam.build();
  exSam.sortLen();
  exSam.getSizeLen();
  int ans = 0;
  for (int i = 0; i < exSam.tot; ++i) {
    bool flag = true;
    for (int j = 0; j < exSam.curString; ++j) {
      if (!exSam.sizeC[i][j]) {
        flag = false;
        break;
      }
    }
    if (flag) ans = max(ans, exSam.len[i]);
  }
  cout << ans << endl;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用