Skip to content

Suffix Tree

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

Some Notation

Let the string used to build the suffix tree be denoted as \(S\), with length \(n\) and alphabet \(\Sigma\).

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

Let \(S [l, r]\) denote the substring of \(S\) from the \(l\)-th character to the \(r\)-th character.

Let \(S [i, n]\) be the suffix of \(S\) starting at \(i\), and \(S [1, i]\) be the prefix of \(S\) ending at \(i\).

Definition

The suffix trie of a string \(S\) is the trie obtained by inserting all suffixes of \(S\) into a trie. In the suffix trie, the string corresponding to node \(x\) is the concatenation of characters along the path from the root to \(x\). Nodes in the suffix trie that correspond to some suffix of \(S\) are called suffix nodes.

It is easy to see the advantageous property of the suffix trie: its non-root nodes exactly accept all distinct non-empty substrings of \(S\). However, both the time and space complexity of building a suffix trie are \(O(n^2)\), which is unacceptable in many cases. Therefore, we introduce the concept of the suffix tree.

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

In both the suffix tree and the implicit suffix tree, each edge corresponds to a string; each non-root node \(x\) corresponds to a set of strings, which are any non-empty prefix of the string on the edge from \(x\)'s parent \(fa_x\) to \(x\), concatenated with the string from the root to \(fa_x\), denoted as \(str_x\). Additionally, in the implicit suffix tree, a suffix that does not correspond to any node is called an implicit suffix.

The figure below shows, from left to right, the suffix trie, suffix tree, and implicit suffix tree built for the string \(\texttt{cabab}\).

suffix-tree_cabab1.png

Consider inserting the suffixes of \(S\) one by one into the suffix trie. Starting from the second insertion, at most one node with more than one child and one suffix node are added each time. Therefore, the number of nodes in the suffix tree is at most \(2n\), which is very efficient.

Construction of Suffix Trees

Algorithm Supporting Front-End Dynamic Character Addition

The parent tree constructed by building a SAM (Suffix Automaton) on the reversed string is exactly the suffix tree of the original string. Therefore, we can build the SAM by adding characters of the reversed string one by one.

Reference Implementation 
 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
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 Back-End Dynamic Character Addition

Ukkonen's algorithm is an incremental construction algorithm. We insert each character of the string \(S\) into the tree sequentially and correctly maintain the current suffix tree after each insertion.

Naive Algorithm

First, we introduce a more brute-force construction method, using the string \(\texttt {abbbc}\) as an example.

Initially, create a root node, denoted as node \(0\). Each edge maintains an interval \([l,r]\) indicating that the string on this edge is \(S[l,r]\). Additionally, maintain the number of inserted characters \(m\), initially \(0\).

First, insert character \(\texttt a\). Simply extend an edge from node \(0\), labeled \([1,\infty]\), pointing to a newly created node. Here, \(\infty\) is a large value, understood as the end of the string, so that when new characters are inserted, this edge will automatically include the new character.

suffix-tree_a.webp

Next, we insert character \(\texttt b\). Again, extend an edge from \(0\), labeled \([2,\infty]\). Note that the meaning of the previously extended edge \([1,\infty]\) automatically changes: as the end of the string moves, the string it represents changes from \(\texttt a\) to \(\texttt {ab}\). This is correct because all previous suffixes already appear as leaf nodes in the tree; we only need to insert the current character at the end of all leaf nodes.

suffix-tree_ab.webp

Next, we want to insert another character \(\texttt b\). However, \(\texttt b\) is already a substring of the previously inserted string, so the original tree already contains \(\texttt b\). At this point, we do nothing and record a \(k\) such that \(S[k,m]\) is the current longest implicit suffix.

suffix-tree_abb.webp

Next, we insert another \(\texttt b\). Since the previous \(\texttt b\) was not inserted successfully, \(k=3\), meaning the suffix to insert is \(\texttt {bb}\). We start from the root and search for \(\texttt {bb}\), finding it also in the original tree. Again, we do nothing.

suffix-tree_abbb.webp

Note that we ignore suffixes after \(k\). If \(S[k,m]\) is an implicit suffix, then for any \(l>k\), \(S[l,m]\) are also implicit suffixes. Because \(S[k,m]\) being an implicit suffix implies there exists a character \(c\) such that \(S[k, m] + c\) is a substring of \(S\), so \(S [ l, m] + c\) is also a substring of \(S\). By the definition of the implicit suffix tree, \(S[ l, m]\) does not appear as a leaf node either.

Next, we insert \(\texttt c\). At this point, \(k=3\), so we need to follow from the root to find \(\texttt {bbc}\), which is not in the original tree. We need to extend an outgoing edge labeled \([5,\infty]\) at the node representing \(\texttt {bb}\). However, we find that this node does not actually exist but is contained within an edge. Therefore, we need to split this edge, create a new node, and then extend the desired outgoing edge from the created node. The insertion is now successful, and we set \(k\to k+1\) because \(S[k,m]\) is no longer an implicit suffix.

suffix-tree_abbbc1.webp

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

suffix-tree_abbbc2.webp

The construction process ends.

The worst-case complexity of this algorithm, which brute-forces from the root for each insertion, is \(O(n)\), so the total complexity is \(O(n^2)\).

The naive algorithm is slow mainly because each extend operation requires traversing from the root to find the insertion position of the longest implicit suffix. Therefore, consider recording this position. First, we use a pair \((now,rem)\) to describe the current longest implicitly contained suffix \(S[k,m]\). Starting from node \(now\), following the outgoing edge beginning with \(S[m-rem+1]\) for length \(rem\) should uniquely represent a string. When inserting a new character, we only need to search from the position described by \((now,rem)\).

Now, we only need to update \((now,rem)\) when \(k\to k + 1\). If \(now=0\), simply let \(rem \to rem-1\), because the next suffix to insert is the previous one with length decreased by \(1\). 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 a lemma: For any non-leaf, non-root node \(x\) in the 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 the first character removed.

Proof. Let \(s\) be the string formed by removing the first character from \(str_x\). By the definition of the implicit suffix tree, there exist two distinct characters \(c_1,c_2\) such that \(str_x + c1\) and \(str_x + c_2\) are both substrings of \(S\). Therefore, \(s + c_1\) and \(s + c_2\) are also substrings of \(S\), so \(s\) corresponds to a branching key point in the suffix trie, i.e., there exists \(y\) in the implicit suffix trie such that \(str_y=s\). Q.E.D.

From this lemma, we define \(\operatorname{Link}(x)=y\), called the suffix link of \(x\). Then \(now'=\operatorname{Link}(now)\) must exist. Now we only need to compute \(\operatorname{Link}\) for all non-root, non-leaf nodes in the implicit suffix tree.

Ukkonen's Algorithm

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

To build the implicit suffix tree, we add characters of \(S\) from front to back. Assume the root node is \(0\), and the implicit suffix tree for \(S[1, m]\) has been constructed with suffix links maintained. The longest implicit suffix of \(S [1, m]\) is \(S [k, m]\), located at \((now, rem)\) in the tree. Let \(S [m + 1] = x\). Now we need to add character \(x\). At this point, every suffix of \(S [1, m]\) needs to have character \(x\) appended at the end. Since all explicit suffixes correspond to some leaf node in the tree, and their parent edges have right endpoint \(\infty\), they require no maintenance. Therefore, we only need to consider the effect of appending \(x\) to implicit suffixes on the tree structure. First, consider \(S [k, m]\). There are two cases:

  1. There already exists a transition labeled \(x\) at position \((now, rem)\). In this case, the suffix tree structure does not change. Since \(S [k, m+1]\) already appears in the suffix tree, for any \(l > k\), \(S [ l, m + 1]\) will also appear in the suffix tree. We only need to set \(rem\to rem + 1\) without any modifications.
  2. There is no transition labeled \(x\) at position \((now, rem)\). If \((now, rem)\) is exactly a node in the tree, then this node adds an outgoing edge labeled \(x\); otherwise, we need to split the edge, create a new node at this position, and add an outgoing edge labeled \(x\) from the new node. At this point, for \(l > k\), we do not know how \(S [ l, m]\) will affect the suffix tree structure, so we need to continue considering \(S [k + 1, m]\). Consider how to find the position of \(S [k + 1, m]\) in the suffix tree: if \(now\) is not \(0\), we can 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 inserting all characters, so the time complexity is \(O(n)\).

Since Ukkonen's algorithm can only produce the implicit suffix tree of \(S\), and the implicit suffix tree may be less powerful than the suffix tree for some problems, we can append a character that never appears before to the end of \(S\) when needed. Then all suffixes of \(S\) correspond one-to-one with all leaves of the tree.

Reference Implementation 
 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
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 path from a node to the root in a suffix tree is a non-empty substring of \(S\), which is useful for many string problems.

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

Example Problems

Luogu P3804【Template】Suffix Automaton (SAM)

Problem:

Given a string \(S\) consisting only of lowercase letters.

Find the maximum value of (occurrence count multiplied by length) for all substrings of \(S\) that appear more than once.

Solution

Build the implicit suffix tree with a terminating character inserted. Every path from the root in the tree forms a substring. The occurrence count of an explicit suffix is the number of leaf nodes in the subtree of its corresponding node. Implicit suffixes need not be considered because the occurrence count of an implicit suffix equals that of the first explicit suffix node encountered when moving down, and it is certainly not longer than that explicit suffix. Therefore, traverse the entire tree, compute the number of leaves in each node's subtree and the path length from each node to the root. If the leaf count \(>1\), update the answer. Complexity \(O(|S||\Sigma|)\).

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
#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: Given a main string \(S\) of lowercase letters and \(n\) query strings, find the total number of occurrences of all cyclic shifts of each query string \(x_i\) in the main string.

Solution

Build the implicit suffix tree with a terminating character inserted.

Enumerate the current cyclic shift, recording how long a prefix can be matched in the tree.

Repeat a process similar to Ukkonen's algorithm, recording the current matching position \((now,rem)\). Each time, try to insert the next character; if successful, continue inserting; otherwise, break out of the loop.

If a cyclic shift is successfully matched and has not appeared before, update the answer.

When switching to the next cyclic shift, we need to delete the first character of the currently matched substring: this is exactly equivalent to setting \(now \to \operatorname{Link}(now)\). Of course, if \(now=1\), simply set \(rem\to rem-1\).

Complexity \(O(|S||\Sigma|+\sum|x_i|)\).

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
#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 Team Training Paper "Construction of Suffix Trees" by Dai Chenxin
  2. Cool Suffix Tree Magic - EternalAlexander's Blog
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用