Suffix Tree

A suffix tree is a data structure that maintains all suffixes of a string.

Notation

Let $S$ be the original string used to construct the suffix tree, with length $n$ and character set $\Sigma$.

Let $S[i]$ denote the $i$-th character of $S$, where $1 \le i \le n$.

Let $S [l, r]$ denote the string formed by the $l$-th through $r$-th characters of $S$; this is called a substring of $S$.

Let $S [i, n]$ be the suffix of $S$ beginning at $i$, and let $S [1, i]$ be the prefix of $S$ ending at $i$.

Definition

The suffix trie of string $S$ is the trie obtained by inserting all suffixes of S into a trie. In a suffix trie, the string corresponding to node x is the concatenation of the characters along the path from the root to x. Let the nodes in the suffix trie corresponding to some suffix of $S$ be called suffix nodes.

It is easy to see the advantageous property of a suffix trie: its non-root nodes are exactly able to represent all essentially different nonempty substrings of $S$. However, both the time and space complexities of constructing a suffix trie are $O(n^2)$, which is unacceptable in many cases, so we introduce the concept of a suffix tree.

If we regard all nodes in the suffix trie with more than one child and all suffix nodes as key points, and define the compressed trie obtained by retaining only the key points and compressing chains formed by non-key points into single edges as the suffix tree. If we regard only all nodes with more than one child and leaf nodes in the suffix trie as key points, and define the compressed trie obtained by retaining only the key points as the implicit suffix tree. It is easy to see that the implicit suffix tree is obtained by compressing the suffix tree further.

In a suffix tree and an implicit suffix tree, each edge corresponds to a string. Each non-root node $x$ corresponds to a set of strings: the string passed through from the root to $x$'s parent node $fa_x$, concatenated with any nonempty prefix of the string corresponding to the tree edge from $fa_x$ to $x$; this is called $str_x$. In an implicit suffix tree, a suffix with no corresponding node is called an implicit suffix.

The figure below shows, from left to right, the suffix trie, suffix tree, and implicit suffix tree constructed from the original string $\mathtt{cabab}$.

Consider inserting the suffixes of $S$ into the suffix trie one by one. Starting from the second insertion, each insertion adds at most one node with more than one child and one suffix node, so the suffix tree has at most $2n$ nodes, which is excellent.

Constructing a Suffix Tree

Algorithm Supporting Dynamic Addition of Characters at the Front

The parent tree of the SAM built from the reversed string is the suffix tree of this string, so we only need to add the characters of the reversed string to the SAM one by one.

struct SuffixAutomaton {
  int tot, lst;
  int siz[N << 1];
  int buc[N], id[N << 1];

  struct Node {
    int len, link;
    int ch[26];
  } st[N << 1];

  SuffixAutomaton() : tot(1), lst(1) {}

  void extend(int ch) {
    int cur = ++tot, p = lst;
    lst = cur;
    siz[cur] = 1, st[cur].len = st[p].len + 1;
    for (; p && !st[p].ch[ch]; p = st[p].link) st[p].ch[ch] = cur;
    if (!p)
      st[cur].link = 1;
    else {
      int q = st[p].ch[ch];
      if (st[q].len == st[p].len + 1)
        st[cur].link = q;
      else {
        int pp = ++tot;
        st[pp] = st[q];
        st[pp].len = st[p].len + 1;
        st[cur].link = st[q].link = pp;
        for (; p && st[p].ch[ch] == q; p = st[p].link) st[p].ch[ch] = pp;
      }
    }
  }
} SAM;

Algorithm Supporting Dynamic Addition of Characters at the Back

Ukkonen's algorithm is an incremental construction algorithm. We insert each character of string $S$ into the tree in order and correctly maintain the current suffix tree after every insertion.

Naive algorithm

First, let us introduce a relatively brute-force construction method. We use the string $\texttt {abbbc}$ to demonstrate the construction process.

Initially, create a root node, called node $0$. For each edge, maintain an interval $[l,r]$ representing the string on that edge as $S[l,r]$. Also maintain the number of inserted characters $m$, initially $0$.

First insert character $\texttt a$. Directly extend an edge from node $0$, label it $[1,\infty]$, and point it to a newly created node. Here $\infty$ is an extremely large value that can be understood as the end of the string; thus, when a new character is inserted, this edge automatically includes the new character.

Next insert character $\texttt b$. Similarly, extend an edge from node $0$, label it $[2,\infty⁡]$. Notice that the meaning of the previously extended edge $[1,\infty]$ changes automatically: as the end of the string changes, the string it represents changes from $\texttt a$ to $\texttt {ab}$. This is correct, because all previous suffixes have already appeared in the tree as leaf nodes, so we only need to insert the current character at the end of every leaf node.

Next, we insert another character $\texttt b$. However, $\texttt b$ is a substring of the string already inserted, so the existing tree already contains $\texttt b$. At this point, we do nothing and record a $k$ indicating that $S[k,m]$ is the current longest implicit suffix.

Next insert another $\texttt b$. Because the previous $\texttt b$ was not inserted successfully, we now have $k=3$, meaning that the suffix to insert is $\texttt {bb}$. We search downward from the root for $\texttt {bb}$ and find that it is also already in the original tree. Again, we do nothing.

Notice that we did not handle the suffixes after $k$. If $S[k,m]$ is an implicit suffix, then for $l>k$, $S[l,m]$ is also an implicit suffix. Since $S[k,m]$ being an implicit suffix implies that there exists a character $c$ such that $S[k, m] + c$ is a substring of $S$, $S [ l, m] + c$ is also a substring of $S$. By the definition of an implicit suffix tree, $S[ l, m]$ also does not appear as a leaf node.

Next we insert $\texttt c$. Since $k=3$, we need to search downward from the root for $\texttt {bbc}$ and find that it is not in the original tree. We need to extend an outgoing edge labeled $[5,\infty]$ from the node represented by $\texttt {bb}$. However, this node does not actually exist; it lies inside an edge, so we need to split that edge, create a new node, and then extend the outgoing edge we want to create from the new node. The insertion now succeeds, so set $k\to k+1$, because $S[k,m]$ is no longer an implicit suffix.

Next, because $k$ changed, we repeat this process until an implicit suffix appears again or $k>m$ (the latter occurs in this example).

The construction process ends.

The worst-case complexity of searching downward from the root and inserting by brute force each time is $O(n)$, so the total complexity is $O(n^2)$.

Suffix Links

The naive algorithm is slow mainly because each extend must find the insertion position of the longest implicit suffix starting from the root. Therefore, consider recording this position. First, use a pair $(now,rem)$ to describe the current longest implicitly contained suffix $S[k,m]$. Following the outgoing edge from node $now$ that starts with $S[m-rem+1]$ for a length of $rem$ should reach a position that uniquely represents a string. Each time a new character is inserted, we only need to search from the position described by $now$ and $rem$.

Now we only need to update $(now,rem)$ when $k\to k + 1$. If $now=0$, we only need to set $rem \to rem-1$, because the next suffix to insert has length $-1$ of the one just inserted. Otherwise, let the substring corresponding to $str_{now}$ be $S[l,r]$. We need to find a node $now'$ corresponding to $S[l+1,r]$ and set $now\to now'$.

First, we have the following lemma: for any non-leaf, non-root node $x$ in an implicit suffix tree, there exists another non-leaf node $y$ in the tree such that $str_y$ is the substring corresponding to $str_x$ with its first character removed.

Proof. Let $s$ denote the string formed by removing the first character from $str_x$. By the definition of an implicit suffix tree, there exist two different characters $c_1,c_2$ such that both $str_x + c1$ and $str_x + c_2$ are substrings of $S$. Therefore, $s + c_1$ and $s + c_2$ are also substrings of $S$, so $s$ also corresponds to a branching key point in the suffix trie. Thus, in the implicit suffix trie there is a $y$ such that $str_y=s$. QED.

By this lemma, define $\operatorname{Link}(x)=y$, called the Suffix Link of x. Thus $now'=\operatorname{Link}(now)$ must exist. We only need to find $\operatorname{Link}$ for every non-root, non-leaf node in the implicit suffix tree.

Ukkonen's Algorithm

The overall process of Ukkonen's algorithm is as follows:

To construct the implicit suffix tree, add the characters of $S$ from front to back. Suppose the root node is $0$, the implicit suffix tree for $S[1, m]$ has been constructed, and the suffix links have been maintained. The longest implicit suffix of $S [1, m]$ is $S [k, m]$, whose position in the tree is $(now, rem)$. Let $S [m + 1] = x$; we now need to add character x. At this point, character $x$ must be appended to the end of every suffix of $S [1, m]$. Since every explicit suffix corresponds to a leaf node in the tree and the right endpoint of its parent edge is $\infty$, no maintenance is needed. Thus, we only need to consider the effect of appending $x$ to the end of an implicit suffix on the shape of the tree. First consider $S [k, m]$; there are two cases:

1. The position $(now, rem)$ already has a transition for $x$. The shape of the suffix tree does not change. Since $S [k, m+1]$ has already appeared in the suffix tree, for $l > k$, $S [ l, m + 1]$ will also appear in the suffix tree. We only need to set $rem\to rem + 1$, without making any modification.
2. The position $(now, rem)$ has no transition for $x$. If $(now, rem)$ happens to be a node in the tree, add an outgoing edge $x$ to this node; otherwise, split the node, add a new node at this position, and add an outgoing edge $x$ at the new node. For $l > k$, we do not know what effect $S [ l, m]$ will have on the shape of the suffix tree, so we must continue considering $S [k + 1, m]$. To find the position of $S [k + 1, m]$ in the suffix tree: if $now$ is not $0$, use the suffix link and set $now = \operatorname{Link}(now)$; otherwise, set $rem\to rem − 1$. Finally set $k\to k + 1$ and repeat this process.

Each step takes only constant time, and the algorithm stops after all characters have been inserted, so the time complexity is $O(n)$.

Since Ukkonen's algorithm can only construct the implicit suffix tree of $S$, and an implicit suffix tree may be less powerful than a suffix tree for some problems, when necessary, a character that has never appeared can be added to the end of $S$, so that all suffixes of S correspond one-to-one with all leaves of the tree.

struct SuffixTree {
  int ch[M + 5][RNG + 1], st[M + 5], len[M + 5], link[M + 5];
  int s[N + 5];
  int now{1}, rem{0}, n{0}, tot{1};

  SuffixTree() { len[0] = inf; }

  int new_node(int s, int le) {
    ++tot;
    st[tot] = s;
    len[tot] = le;
    return tot;
  }

  void extend(int x) {
    s[++n] = x;
    ++rem;
    for (int lst{1}; rem;) {
      while (rem > len[ch[now][s[n - rem + 1]]])
        rem -= len[now = ch[now][s[n - rem + 1]]];
      int &v{ch[now][s[n - rem + 1]]}, c{s[st[v] + rem - 1]};
      if (!v || x == c) {
        lst = link[lst] = now;
        if (!v)
          v = new_node(n, inf);
        else
          break;
      } else {
        int u{new_node(st[v], rem - 1)};
        ch[u][c] = v;
        ch[u][x] = new_node(n, inf);
        st[v] += rem - 1;
        len[v] -= rem - 1;
        lst = link[lst] = v = u;
      }
      if (now == 1)
        --rem;
      else
        now = link[now];
    }
  }
} Tree;

Applications

Every node on a suffix tree has a path to the root that is a nonempty substring of $S$, which is useful for handling many string problems.

The DFS order of a suffix tree is the suffix array. A subtree of a suffix tree therefore corresponds to an interval in the suffix array. The longest common prefix of two suffixes in a suffix tree is the LCA of their corresponding leaf nodes. Therefore, the conclusion about the height of a suffix array can be understood as saying that the LCA of several nodes in the tree equals the LCA of the nodes with the smallest and largest DFS orders.

Examples

Luogu P3804【Template】Suffix Automaton (SAM)

Problem statement:

Given a string $S$ containing only lowercase letters.

Find the maximum, over all substrings of $S$ whose number of occurrences is not $1$, of the number of occurrences multiplied by the length of the substring.

#include <iostream>
#include <string>
using namespace std;
constexpr int N(1e6), M(2 * N), inf(1e7), RNG{26};

struct SuffixTree {
  int ch[M + 5][RNG + 1], st[M + 5], len[M + 5], link[M + 5];
  int s[N + 5];
  int now{1}, rem{0}, n{0}, tot{1};

  SuffixTree() { len[0] = inf; }

  int new_node(int s, int le) {
    ++tot;
    st[tot] = s;
    len[tot] = le;
    return tot;
  }

  void extend(int x) {
    s[++n] = x;
    ++rem;
    for (int lst{1}; rem;) {
      while (rem > len[ch[now][s[n - rem + 1]]])
        rem -= len[now = ch[now][s[n - rem + 1]]];
      int &v{ch[now][s[n - rem + 1]]}, c{s[st[v] + rem - 1]};
      if (!v || x == c) {
        lst = link[lst] = now;
        if (!v)
          v = new_node(n, inf);
        else
          break;
      } else {
        int u{new_node(st[v], rem - 1)};
        ch[u][c] = v;
        ch[u][x] = new_node(n, inf);
        st[v] += rem - 1;
        len[v] -= rem - 1;
        lst = link[lst] = v = u;
      }
      if (now == 1)
        --rem;
      else
        now = link[now];
    }
  }

  pair<long long, int> search(int u, int dep = 0) {
    if (st[u] + len[u] >= n) return {0, 1};
    dep += len[u];
    long long ans{0};
    int ys{0};
    for (int i{0}; i <= RNG; ++i)
      if (ch[u][i]) {
        auto res = search(ch[u][i], dep);
        ans = max(ans, res.first);
        ys += res.second;
      }
    if (ys > 1) ans = max(ans, 1LL * dep * ys);
    return {ans, ys};
  }
} T;

string s;

int main() {
  cin >> s;
  for (int i = 0; i < s.size(); ++i) T.extend(s[i] - 'a' + 1);
  T.extend(0);
  cout << T.search(1).first << endl;
  return 0;
}

CF235C Cyclical Quest

Problem statement: Given a lowercase main string $S$ and $n$ query strings, find the sum, for each query string $x_i$, of the numbers of occurrences of all its cyclic shifts in the main string.

#include <cstring>
#include <iostream>
#include <string>
using namespace std;
constexpr int N(1e6);

struct SuffixTree {
  static constexpr int N{2 * ::N}, RNG{26}, inf = 1e7;
  int ch[N + 5][RNG + 1];
  int st[N + 5], len[N + 5], link[N + 5], s[::N + 5];
  int now{1}, rem{0}, tot{1}, n{0};
  int cnt[N + 5], vis[N + 5];

  SuffixTree() { len[0] = inf; }

  void clear() {
    memset(ch, 0, sizeof ch);
    now = tot = 1;
    rem = n = 0;
  }

  int new_node(int s, int le) {
    ++tot;
    st[tot] = s;
    len[tot] = le;
    return tot;
  }

  void extend(int x) {
    s[++n] = x;
    ++rem;
    for (int lst{1}; rem;) {
      while (rem > len[ch[now][s[n - rem + 1]]])
        rem -= len[now = ch[now][s[n - rem + 1]]];
      int &v{ch[now][s[n - rem + 1]]}, c{s[st[v] + rem - 1]};
      if (!v || x == c) {
        lst = link[lst] = now;
        if (!v)
          v = new_node(n, inf);
        else
          break;
      } else {
        int u{new_node(st[v], rem - 1)};
        ch[u][c] = v;
        ch[u][x] = new_node(n, inf);
        st[v] += rem - 1;
        len[v] -= rem - 1;
        lst = link[lst] = v = u;
      }
      if (now == 1)
        --rem;
      else
        now = link[now];
    }
  }

  void init(int u) {
    if (len[u] > 1e6) return cnt[u] = 1, void();
    for (int i{0}; i <= RNG; ++i)
      if (ch[u][i]) init(ch[u][i]), cnt[u] += cnt[ch[u][i]];
  }

  long long test(const char *t, int m) {
    static int time{0};
    ++time;
    int now{1}, rem{0}, o{0};
    long long ans{0};
    for (int i{1}; i <= m; ++i) {
      while (o < i + m - 1) {
        while (rem >= len[ch[now][t[o - rem + 1]]])
          rem -= len[now = ch[now][t[o - rem + 1]]];
        int v{ch[now][t[o - rem + 1]]}, c{s[st[v] + rem]};
        if (v && c == t[o + 1]) {
          ++o;
          ++rem;
        } else {
          break;
        }
      }
      if (o == i + m - 1 && vis[ch[now][t[o - rem + 1]]] != time)
        ans += cnt[ch[now][t[o - rem + 1]]],
            vis[ch[now][t[o - rem + 1]]] = time;
      if (now == 1)
        --rem;
      else
        now = link[now];
    }
    return ans;
  }
} T;

string s;

int main() {
  cin >> s;
  for (int i = 0; i < s.size(); ++i) T.extend(s[i] - 'a' + 1);
  T.extend(0);
  T.init(1);
  int pw;
  cin >> pw;
  while (pw--) {
    cin >> s;
    int n = s.size();
    for (auto &ch : s) ch += 1 - 'a';
    s = " " + s + s;
    cout << T.test(s.data(), n) << "\n";
  }
  return 0;
}

References

1. 2021 National Training Team paper "Constructing a Suffix Tree" by Chen Chenxin
2. Cool Suffix Tree Magic - EternalAlexander's Blog