跳转至

後綴樹

後綴樹是一種維護一個字符串所有後綴的數據結構。

一些記號

記構建後綴樹的母串為 \(S\)，長度為 \(n\)，字符集為 \(\Sigma\)。

令 \(S[i]\) 表示 \(S\) 中的第 \(i\) 個字符，其中 \(1 \le i \le n\)。

令 \(S [l, r]\) 表示 \(S\) 中第 \(l\) 個字符至第 \(r\) 個字符組成的字符串，稱為 \(S\) 的一個子串。

記 \(S [i, n]\) 為 \(S\) 的以 \(i\) 開頭的後綴，\(S [1, i]\) 為 \(S\) 的以 \(i\) 結尾的前綴。

定義

定義字符串 \(S\) 的 後綴 trie 為將 S 的所有後綴插入至 trie 樹中得到的字典樹。在後綴 trie 中，節點 x 對應的字符串為從根節點走到 x 的路徑上經過的字符拼接而成的字符串。記後 綴 trie 中所有對應 \(S\) 的某個後綴的節點為後綴節點。

容易看出後綴 trie 的優越性質：它的非根節點恰好能接受 \(S\) 的所有本質不同非空子串。但構建後綴 trie 的時空複雜度均為 \(O(n^2)\)，在很多情況下不能接受，所以我們引入後綴樹的概念。

如果令後綴 trie 中所有擁有多於一個兒子的節點和後綴節點為關鍵點，定義只保留關鍵點，將非關鍵點形成的鏈壓縮成一條邊形成的壓縮 trie 樹為 後綴樹 (Suffix Tree)。如果僅令後綴 trie 中所有擁有多於一個兒子的節點和葉結點為關鍵點，定義只保留關鍵點形成的壓縮 trie 樹為 隱式後綴樹 (Implicit Suffix Tree)。容易看出隱式後綴樹為後綴樹進一步壓縮後得到的結果。

在後綴樹和隱式後綴樹中，每條邊對應一個字符串；每個非根節點 \(x\) 對應了一個字符串集合，為從根節點走到 \(x\) 的父親節點 \(fa_x\) 經過的字符串，拼接上 \(fa_x\) 至 \(x\) 的樹邊對應的字符串的任意一個非空前綴，稱為 \(str_x\)。同時，在隱式後綴樹中，稱一個沒有對應任何節點的後綴為 隱式後綴。

下圖從左至右分別為以字符串 \(\texttt{cabab}\) 為母串構建的後綴 trie、後綴樹和隱式後綴樹。

suffix-tree_cabab1.png

考慮將 \(S\) 的後綴逐個插入至後綴 trie 中。從第二次插入開始，每次最多新增一個擁有多於一個兒子的節點和一個後綴節點，所以後綴樹中節點個數最多為 \(2n\) 個，十分優秀。

後綴樹的建立

支持前端動態添加字符的算法

反串建 SAM 建出的 parent 樹就是這個串的後綴樹，所以我們將反串的字符逐個加入 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
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;

支持後端動態添加字符的算法

Ukkonen 算法是一種增量構造算法。我們依次向樹中插入串 \(S\) 的每一個字符，並在每一次插入之後正確地維護當前的後綴樹。

樸素算法

首先介紹一下一種較為暴力的構建方式，我們用字符串 \(\texttt {abbbc}\) 來演示一下構建的過程。

初始建立一個根節點，稱為 \(0\) 號節點。同時每條邊我們維護一個區間 \([l,r]\) 表示這條邊上的字符串為 \(S[l,r]\)。另外，維護已經插入的字符個數 \(m\)，初始為 \(0\)。

首先插入字符 \(\texttt a\)，直接從 \(0\) 號節點伸出一條邊，標為 \([1,\infty]\)，指向一個新建的節點。這裏的 \(\infty\) 是一個極大值，可理解為串的結尾，這樣在插入新字符時，這條邊會自動的包含新的字符。

suffix-tree_a.webp

接下來我們插入字符 \(\texttt b\)，同樣從 \(0\) 伸出一條邊，標為 \([2,\infty⁡]\)。注意到之前延伸出的邊 \([1,\infty]\) 的意義自動地發生了變化，隨着串結尾的改變，其表示的串從 \(\texttt a\) 變為了 \(\texttt {ab}\)。這樣是正確的，因為之前所有後綴都已經以一個葉節點的形式出現在樹中，只需要向所有葉節點的末端插入一個當前字符即可。

suffix-tree_ab.webp

接下來，我們要再次插入一個字符 \(\texttt b\)，但是 \(\texttt b\) 是之前已經插入的字符串的一個子串，因此原樹已經包含 \(\texttt b\)，此時，我們什麼都不做，記錄一個 \(k\) 表示 \(S[k,m]\) 是當前最長的隱式後綴。

suffix-tree_abb.webp

接下來我們插入另一個 \(\texttt b\)。因為前一個 \(\texttt b\) 沒有插入成功，此時 \(k=3\)，代表要插入的後綴為 \(\texttt {bb}\)。我們從根開始向下尋找 \(\texttt {bb}\)，發現也在原樹之中。同樣，我們還是什麼都不做。

suffix-tree_abbb.webp

注意到我們沒有管 \(k\) 之後的後綴。因為如果 \(S[k,m]\) 是一個隱式後綴，那麼對於 \(l>k\)，\(S[l,m]\) 都是隱式後綴。因為由 \(S[k,m]\) 為隱式後綴可知，存在字符 \(c\) 使得 \(S[k, m] + c\) 為 \(S\) 的子串，所以 \(S [ l, m] + c\) 也為 \(S\) 的子串，由隱式後綴樹的定義可知 \(S[ l, m]\) 也不作為葉結點出現。

接下來我們插入 \(\texttt c\)，此時 \(k=3\)，因此我們需要沿着根向下尋找 \(\texttt {bbc}\)，發現不在原樹中。我們需要在 \(\texttt {bb}\) 處代表的節點延伸出一條為 \([5,\infty]\) 的出邊。但發現這個節點其實不存在，而是包含在一條邊中，因此我們需要分裂這條邊，創建一個新節點，再在創建的節點處伸展出我們要創建的出邊。此時成功插入，令 \(k\to k+1\)，因為 \(S[k,m]\) 不再是隱式後綴。

suffix-tree_abbbc1.webp

接下來，因為 \(k\) 變化了，我們重複這個過程，直到再次出現隱式後綴，或 \(k>m\)（在這個例子中，是後者）。

suffix-tree_abbbc2.webp

構建過程結束。

該算法每次暴力從根向下尋找並插入的複雜度最壞為 \(O(n)\)，所以總的複雜度為 \(O(n^2)\)。

後綴鏈接

樸素算法慢主要是因為每次 extend 都要從根找到最長隱式後綴的插入位置。所以考慮把這個位置記下來。首先，我們採用一個二元組 \((now,rem)\) 來描述當前這個最長的被隱式包含的後綴 \(S[k,m]\)。沿着節點 \(now\) 的開頭為 \(S[m-rem+1]\) 的出邊走長度 \(rem\) 到達的位置應該唯一表示一個字符串，每次插入新的字符時，我們只需要從 \(now\) 和 \(rem\) 描述的位置查找即可。

現在，我們只需要在 \(k\to k + 1\) 時更新 \((now,rem)\)。此時如果 \(now=0\)，只需要讓 \(rem \to rem-1\)，因為下一個要插入的後綴是剛才插入的長度 \(-1\)。否則，設 \(str_{now}\) 對應的子串為 \(S[l,r]\)，我們需要找到一個節點 \(now'\) 對應 \(S[l+1,r]\)，令 \(now\to now'\) 即可。

首先有引理：對隱式後綴樹中任意非葉非根節點 \(x\)，在樹中存在另一非葉節點 \(y\)，使得 \(str_y\) 是 \(str_x\) 對應的子串刪去開頭的字符。

證明。令 \(s\) 表示 \(str_x\) 刪去開頭字符形成的字符串。由隱式後綴樹的定義可知，存在兩個不同的字符 \(c_1,c_2\)，滿足 \(str_x + c1\) 與 \(str_x + c_2\) 均為 \(S\) 的子串。所以，\(s + c_1\) 與 \(s + c_2\) 也為 \(S\) 的子串，所以 \(s\) 在後綴 trie 中也對應了一個有分叉的關鍵點，即在隱式後綴 trie 中存在 \(y\) 使得 \(str_y=s\)。證畢。

由該引理，我們定義 \(\operatorname{Link}(x)=y\)，稱為 x 的 後綴鏈接 (Suffix Link)。於是 \(now'=\operatorname{Link}(now)\) 一定存在。現在我們只要能求出隱式後綴樹中所有非根非葉節點的 \(\operatorname{Link}\) 即可。

Ukkonen 算法

Ukkonen 算法的整體流程如下：

為了構建隱式後綴樹，我們從前往後加入 \(S\) 中的字符。假設根節點為 \(0\)，且當前已經建出 \(S[1, m]\) 的隱式後綴樹且維護好了後綴鏈接。\(S [1, m]\) 的最長隱式後綴為 \(S [k, m]\)，在樹中的位置為 \((now, rem)\)。設 \(S [m + 1] = x\), 現在我們需要加入字符 \(x\)。此時，\(S [1, m]\) 的每一個後綴都需要在末尾添加字符 \(x\)。由於所有顯式後綴都對應樹中某個葉結點，它們父邊右端點為 \(\infty\)，無需維護。所以，現在我們只用考慮隱式後綴末尾添加 x 對樹的形態產生的影響。首先考慮 \(S [k, m]\)，有兩種情況：

  1. \((now, rem)\) 位置已經存在 \(x\) 的轉移。此時後綴樹形態不會發生變化。由於 \(S [k, m+1]\) 已經在後綴樹中出現，所以對於 \(l > k\)，\(S [ l, m + 1]\) 也會在後綴樹中出現，此時只需將 \(rem\to rem + 1\)，不需做任何修改。
  2. \((now, rem)\) 不存在 \(x\) 的轉移。如果 \((now, rem)\) 恰好為樹中的節點，則此節點新增一條出邊 \(x\)；否則需要對節點進行分裂，在此位置新增一個節點，並在新增節處添加出邊 \(x\)。此時對於 \(l > k\)，我們並不知道 \(S [ l, m]\) 會對後綴樹形態造成什麼影響，所以我們還需繼續考慮 \(S [k + 1, m]\)。考慮怎麼求出 \(S [k + 1, m]\) 在後綴樹中的位置：如果 \(now\) 不為 \(0\)，可以利用後綴鏈接，令 \(now = \operatorname{Link}(now)\)；否則，令 \(rem\to rem − 1\)。最後令 \(k\to k + 1\)，再次重複這個過程。

每一步都只消耗常數時間，而算法在插入全部的字符後停止，所以時間複雜度為 \(O(n)\)。

由於 Ukkonen 算法只能處理出 \(S\) 的隱式後綴樹，而隱式後綴樹在一些問題中的功能可能不如後綴樹強大，所以在需要時，可以在 \(S\) 的末端添加一個從未出現過的字符，這時 S 的所有後綴可以和樹的所有葉子一一對應。

參考實現 
 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;

作用

後綴樹上每一個節點到根的路徑都是 \(S\) 的一個非空子串，這在處理很多字符串問題時都很有用。

後綴樹的 DFS 序就是後綴數組。後綴樹的一個子樹也就對應到後綴數組上的一個區間。後綴樹上兩個後綴的最長公共前綴是它們對應的葉節點的 LCA，因此，後綴數組的 height 的結論可以理解為樹上若干個節點的 LCA 等於 DFS 序最小的和最大的節點的 LCA。

例題

洛谷 P3804【模板】後綴自動機（SAM）

題意：

給定一個只包含小寫字母的字符串 \(S\)。

請你求出 \(S\) 的所有出現次數不為 \(1\) 的子串的出現次數乘上該子串長度的最大值。

解法

建出插入一個終止符的隱式後綴樹。樹上每條從根出發的路徑都構成子串。一個顯示後綴的出現次數即為對應節點子樹內的葉子節點個數，隱式後綴不用考慮，因為一個隱式後綴的出現次數等於向下走到的第一個節點對應顯示後綴的出現次數，而且一定沒有該顯示後綴長。所以遍歷整棵樹，求出每個節點子樹內葉子個數和每個節點到根的路徑長度。如果葉子個數 \(>1\) 則更新答案。複雜度 \(O(|S||\Sigma|)\)。

參考代碼 
 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
#include <bits/stdc++.h>
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 [__, _]{search(ch[u][i], dep)};
        ans = max(ans, __);
        ys += _;
      }
    if (ys > 1) ans = max(ans, 1LL * dep * ys);
    return {ans, ys};
  }
} T;

char s[N + 5];

int main() {
  scanf("%s", s + 1);
  for (int i{1}; s[i]; ++i) T.extend(s[i] - 'a' + 1);
  T.extend(0);
  cout << T.search(1).first << endl;
  return 0;
}

CF235C Cyclical Quest

題意：給定一個小寫字母主串 \(S\) 和 \(n\) 個詢問串，求每個詢問串 \(x_i\) 的所有循環同構在主串中出現的次數總和。

解法

建立插入終止符的隱式後綴樹。

枚舉當前在那個循環節，記錄在樹上能查找到多長的前綴。

重複類似 Ukkonen 算法的過程，記錄當前能匹配到的位置 \((now,rem)\)。每次嘗試插入下一個字符，如果成功則繼續插入，否則跳出循環。

如果某一個次成功匹配了當前的循環節，且該循環節之前沒出現過，則更新答案。

然後切換到下個循環節的時候，我們要刪去當前匹配的子串開頭的字符：這正好就相當於令 \(now \to \operatorname{Link}(now)\)。當然，如果 \(now=1\) 則直接讓 \(rem\to rem-1\) 就行了。

複雜度 \(O(|S||\Sigma|+\sum|x_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
 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
#include <bits/stdc++.h>
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;

char s[N * 2 + 5];

int main() {
  scanf("%s", s + 1);
  for (int i{1}; s[i]; ++i) T.extend(s[i] - 'a' + 1);
  T.extend(0);
  T.init(1);
  int pw;
  cin >> pw;
  while (pw--) {
    scanf("%s", s + 1);
    int n{strlen(s + 1)};
    for (int i{1}; i <= n; ++i) s[i] += 1 - 'a';
    copy(s + 1, s + 1 + n, s + 1 + n);
    cout << T.test(s, n) << "\n";
  }
  return 0;
}

參考文獻

  1. 2021 國家集訓隊論文《後綴樹的構建》代晨昕
  2. 炫酷後綴樹魔術 - EternalAlexander 的博客
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用