Skip to content

Generalized Suffix Automaton

Prerequisites

The generalized suffix automaton is based on the following knowledge:

Please ensure you are very familiar with the above two topics before reading this article, especially having a certain understanding of the suffix link in the Suffix Automaton.

Introduction

Origin

The generalized suffix automaton was proposed by Liu Yanyi in his 2015 national team paper "Extension of Suffix Automaton on Trie", which directly builds the suffix automaton on a trie.

Most string problems that can be solved with a suffix automaton can be extended to a trie. — Liu Yanyi

Conventions

Refer to String Conventions.

The number of strings is \(k\), i.e., \(S_1, S_2, S_3 \dots S_k\).

The root node of the trie and the generalized suffix automaton is defined as node \(0\).

Overview

The suffix automaton (SAM) is a powerful tool for handling substring problems of a single string.

The generalized suffix automaton (General Suffix Automaton) integrates the suffix automaton into a trie to solve substring problems for multiple strings.

Common Pseudo Generalized Suffix Automata

  1. Concatenate multiple strings directly with special symbols, then build the SAM.
  2. For each string, repeatedly build on the same SAM, resetting the last pointer to zero before each build.

Methods 1 and 2 are simple to implement and often achieve the same correctness as the generalized suffix automaton for many problems. Therefore, many people online choose such implementations. For example, the last application in the suffix automaton article uses method 1 （original link）.

However, both method 1 and method 2 have potentially dangerous time complexities.

Constructing the Generalized Suffix Automaton

According to the original paper, a trie should first be built over the multiple strings, and then the generalized suffix automaton should be constructed based on this trie.

Using the Trie

First, create a trie for the multiple strings. This is not difficult; if you have mastered the prerequisites, you can build it quickly. To unify the code context, a possible trie code is provided below.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
constexpr int MAXN = 2000000;
constexpr int CHAR_NUM = 30;

struct Trie {
  int next[MAXN][CHAR_NUM];  // transitions
  int tot;                   // total number of nodes: [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');
  }
};

Here we obtain a trie built using the next array.

Building the Suffix Automaton

If we directly consider such a trie as a suffix automaton, we can draw the following conclusions:

  • For node i, its len[i] is the same as its depth in the trie.
  • If we perform a topological sort on the trie, we obtain a sequence that is non-decreasing in len. BFS yields the same result.

During the construction of a suffix automaton, it can be viewed as continuously inserting values with strictly increasing len, with a difference of \(1\). Therefore, we can take the result of the topological sort on the trie as a queue and insert nodes into the suffix automaton in this queue order.

In a standard suffix automaton, the len value of the previous node is fixed, i.e., the len of the last node. However, in the generalized suffix automaton, the insertion queue is a non-strictly increasing sequence. So for each value, its last should be known and fixed, which on the trie is its parent node.

Since an approximate suffix automaton is already built in the trie, we only need to process the entire trie structure appropriately to transform it into a generalized suffix automaton. We can update each node on the trie in the order of the queue mentioned earlier. Finally, we obtain the generalized suffix automaton.

For the update operation on each point, we can slightly modify the insertion operation in SAM.

During the entire insertion process, note that since insertion is in non-decreasing len order, during the data copying after clone, we must not copy data whose len is less than the current len.

Process

Based on the above logic, the entire construction process can be described as follows:

  1. Insert all strings into the trie.
  2. Start BFS from the root of the trie, recording the order and the parent node of each node.
  3. Using the obtained BFS sequence in order, build on the original trie for each node, ensuring not to operate on data with len less than the current len.

Proof of Linear Number of Operations

Since only the sequence obtained from BFS is processed, it is guaranteed that each node in the trie is visited only once.

For the worst case, consider the scenario with the maximum number of trie nodes, i.e., when any two strings share no common prefix. Then the number of nodes is \(\sum_{i=1}^{k}|S_i|\), the sum of the lengths of all strings.

The complexity of the update operation in the suffix automaton has been proven in Suffix Automaton.

Thus, it can be proven that the worst-case complexity is linear.

Typically, the average complexity of pseudo generalized suffix automata equals the worst-case complexity of the standard generalized suffix automaton. When dealing with a large number of strings, pseudo generalized suffix automata are far less efficient than standard ones.

Implementation

Only minor necessary modifications to the insertion function are needed to obtain the required function.

Reference Code 
 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];             // node length
  int link[MAXN];            // suffix link, link
  int next[MAXN][CHAR_NUM];  // transitions
  int tot;                   // total number of nodes: [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});
    }
  }
}
  • Since the parent node constantly changes during the BFS process, there is no need to save the last pointer.
  • In the insertion operation, int cur = next[last][c]; differs from the standard suffix automaton's int cur = tot++; because the node we are inserting already exists in the trie structure, so we can directly retrieve it.
  • In the data copying after clone, there is a check: next[clone][i] = len[next[q][i]] != 0 ? next[q][i] : 0;. This differs from the standard suffix automaton's direct assignment next[clone][i] = next[q][i];. This is to avoid updating values with len greater than the current node's len. In the array, len is assigned only after the node is visited by BFS and inserted into the suffix automaton.

Properties

  1. The structure of the generalized suffix automaton is consistent with that of the suffix automaton. Most properties of the suffix automaton also hold for the generalized suffix automaton (Properties of Suffix Automaton).
  2. After the generalized suffix automaton is built, the trie structure is usually destroyed, meaning the generalized suffix automaton generally cannot be used to solve trie problems. Of course, one can allocate double the space and build the suffix automaton in a separate space.

Applications

Number of Distinct Substrings Across All Strings

Based on the properties of the suffix automaton, the number of substrings ending at node \(i\) equals \(len[i] - len[link[i]]\).

Thus, we can sum over all nodes.

Example problem: 【Template】Generalized Suffix Automaton (Generalized SAM)

Reference Code 
  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
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int MAXN = 2000000;  // Double the string length
constexpr int CHAR_NUM = 30;   // Character set size, note to modify the (-'a') below

struct exSAM {
  int len[MAXN];             // Node length
  int link[MAXN];            // Suffix link, link
  int next[MAXN][CHAR_NUM];  // Transitions
  int tot;                   // Total number of nodes: [0, tot)

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

  int insertSAM(int last, int c) {  // last is parent, c is child
    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];  // Node already exists, return directly
    return next[cur][c] = tot++;            // Node does not exist, create node
  }

  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');  // Insert while updating the parent node of the newly inserted node
  }

  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()) {  // Breadth-first search traversal
      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;
}

Longest Common Substring Among Multiple Strings

We need to maintain an array flag of length \(k\) for each node (for this problem, it can be just a marker array; if the count of such substrings is needed, it should be a counting array).

During trie insertion of each string, count for all nodes and store in the array corresponding to the current string.

Then traverse in decreasing order of len, merging the current node's flag with other nodes via suffix links.

Traverse all nodes to find a node with the largest len such that for all k, its flag values are all non-zero. The len of this node is the answer.

Example problem: SPOJ Longest Common Substring II

Reference Code 
  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
126
#include <iostream>
#include <queue>
using namespace std;

constexpr int MAXN = 2000000;  // Double the string length
constexpr int CHAR_NUM = 30;   // Character set size, note to modify the (-'a') below
constexpr int NUM = 15;        // Number of strings

struct exSAM {
  int len[MAXN];             // Node length
  int link[MAXN];            // Suffix link, link
  int next[MAXN][CHAR_NUM];  // Transitions
  int tot;                   // Total number of nodes: [0, tot)
  int lenSorted[MAXN];   // Array sorted by len, only sorting [1, tot)
                         // part, final index range [0, tot - 1)
  int sizeC[MAXN][NUM];  // Represents the number of substrings for a certain string
  int curString;         // Actual number of strings
  /**
   * Auxiliary space array for counting sort
   */
  int lc[MAXN];  // Count array

  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()) {  // Breadth-first search traversal
      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();  // Initialize
  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 协议之条款下提供，附加条款亦可能应用