Generalized suffix automaton

Prerequisite knowledge

The generalized suffix automaton is based on the following topics:

Be sure to become very familiar with the two topics above before reading this article, especially the suffix links in the suffix automaton.

Introduction

Origin

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

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

Conventions

Refer to string conventions.

There are kk strings, namely S1,S2,S3…SkS_1, S_2, S_3 \dots S_k.

The root node of the Trie and the generalized suffix automaton is node 00.

Overview

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

A General Suffix Automaton integrates a suffix automaton into a Trie to solve substring problems involving multiple strings.

Common pseudo-generalized suffix automata

  1. Concatenate multiple strings directly using special symbols, and then build a SAM.
  2. Build on the same SAM repeatedly for each string, setting the last pointer to zero before each construction.

Methods 1 and 2 are simple to implement, and usually achieve the same correctness as a generalized suffix automaton in problems. Therefore, many people on the Internet choose such implementations; for example, the last application in the suffix automaton article uses method 1 original link.

However, the time complexity of both method 1 and method 2 is potentially problematic.

Constructing a generalized suffix automaton

According to the original paper, a Trie should first be built from the multiple strings, and then a generalized suffix automaton should be built on the Trie.

Using a Trie

First, a Trie should be created for the multiple strings. This is not difficult, and if you have mastered the prerequisite knowledge, it can be built quickly. To keep the code context consistent, a possible Trie implementation is given below.

Implementation 
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 regard such a tree directly 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 in nondecreasing order of len. The result of BFS is the same.

During construction, a suffix automaton can be viewed as repeatedly inserting values of len that are strictly increasing, with a difference of 11. Therefore, we can use the result of topologically sorting the Trie as a queue and repeatedly insert nodes into the suffix automaton in the order of that queue.

In an ordinary suffix automaton, the len value of the preceding node is fixed, namely the len of the last node. In a generalized suffix automaton, however, the insertion queue is non-strictly increasing. Therefore, for each value, its last should be known and fixed; in the Trie, it is its parent node.

Since an approximate suffix automaton has already been built in the Trie, it only takes some processing of the overall Trie structure to convert it into a generalized suffix automaton. We can update every node in the Trie according to the queue order described above. Finally, we obtain a generalized suffix automaton.

The update operation for each node can be obtained by slightly modifying the insertion operation in a SAM.

For the whole insertion process, note that because insertion is performed in nondecreasing order of len, during data copying after a clone, data whose len is less than the current len must not be copied.

Process

According to the logic above, the entire construction process can be described as follows:

  1. Insert all strings into the Trie.
  2. Starting from the root of the Trie, perform BFS and record the order and the parent of each node.
  3. Traverse the resulting BFS sequence in order, construct each node in the original Trie, and note that data with len less than the current len must not be operated on.

Proof that the number of operations is linear

Since only the sequence obtained by BFS is processed, every node in the Trie is guaranteed to be visited only once.

For the worst case, consider the case where the Trie itself has the maximum number of nodes: no two strings have a common prefix. Then the number of nodes is ∑i=1k∣Si∣\sum_{i=1}^{k}|S_i|, namely the sum of the lengths of all strings.

The complexity of the update operation in a suffix automaton has already been proved in suffix automaton.

Therefore, its worst-case complexity is linear.

Usually, the average complexity of a pseudo-generalized suffix automaton is equal to the worst-case complexity of a generalized suffix automaton. When faced with a large number of strings, a pseudo-generalized suffix automaton is much less efficient than a standard generalized suffix automaton.

Implementation

The required function can be obtained by making a few necessary modifications to the insertion function.

Reference code 
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 < CHAR_NUM; ++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 < CHAR_NUM; ++i)
        if (next[last][i]) q.push({i, last});
    }
  }
}
  • Because the parent node is constantly changing in the order obtained by the entire BFS process, there is no need to save a last pointer.
  • In the insertion operation, int cur = next[last][c]; differs from the ordinary suffix automaton's int cur = tot++;: because the nodes we insert have already been created in the tree structure, we only need to obtain them directly.
  • In copying data after a clone, there is a check, next[clone][i] = len[next[q][i]] != 0 ? next[q][i] : 0;. This differs from the direct assignment next[clone][i] = next[q][i]; in an ordinary suffix automaton. Here it avoids updating values whose len is greater than the current node's. This is because an array element's len is assigned if and only if that value has been traversed by BFS and inserted into the suffix automaton.

Properties

  1. The generalized suffix automaton has the same structure as a suffix automaton, and most properties of suffix automata also work on generalized suffix automata (properties of suffix automata).
  2. Once a generalized suffix automaton has been built, the Trie structure is usually destroyed, meaning that a generalized suffix automaton generally cannot be used to solve Trie problems. Of course, one can also prepare twice the space and build the suffix automaton in another area of memory.

Applications

Number of distinct substrings among all characters

According to the properties of suffix automata, the number of substrings ending at node ii is equal to len[i]−len[link[i]]len[i] - len[link[i]].

Therefore, we can traverse all nodes and sum them.

Example problem: 【Template】Generalized suffix automaton (generalized SAM)

Reference code 
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int MAXN = 2000000;  // double the total string length
constexpr int CHAR_NUM = 30;   // number of characters; note 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 it
  }

  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 changing the parent of the newly inserted node
  }

  void build() {
    queue<pair<int, int>> q;
    for (int i = 0; i < CHAR_NUM; ++i)
      if (next[0][i]) q.push({i, 0});
    while (!q.empty()) {  // breadth-first traversal
      auto item = q.front();
      q.pop();
      auto last = insertSAM(item.second, item.first);
      for (int i = 0; i < CHAR_NUM; ++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

For each node, we need to create an array flag of length kk (for this problem, it can be just a marker array; if we need to find the number of occurrences of this substring, it should be changed to a counting array).

When inserting strings into the Trie, count all nodes and save the counts in the array corresponding to the current string.

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

Traverse all nodes and find a node with the maximum len such that for all k, the value of its flag is non-00. The lenlen of this node is the answer.

Example problem: SPOJ Longest Common Substring II

Reference code 
#include <iostream>
#include <queue>
using namespace std;

constexpr int MAXN = 2000000;  // double the total string length
constexpr int CHAR_NUM = 30;   // number of characters; note 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 [1, tot) is sorted
                         // final index range is [0, tot - 1)
  int sizeC[MAXN][NUM];  // number of substrings of a given string
  int curString;         // actual number of strings
  /**
   * Auxiliary array used for counting sort
   */
  int lc[MAXN];  // count occurrences

  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 < CHAR_NUM; ++i)
      if (next[0][i]) q.push({i, 0});
    while (!q.empty()) {  // breadth-first traversal
      auto item = q.front();
      q.pop();
      auto last = insertSAM(item.second, item.first);
      for (int i = 0; i < CHAR_NUM; ++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();  // initialization
  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;
}
Previous section
153 Suffix Balanced Tree
Next section
155 Suffix Tree

This content comes from OI Wiki: Generalized suffix automaton. See the original for authors and revision history. AIOJ has adapted the formatting, in-site links, and resource paths.

Content is shared under CC BY-SA 4.0 and SATA license; additional terms are governed by the original notice. Thanks to the OI Wiki authors and contributors; per the SATA terms, please visit the OI Wiki repository and star it to show your support.