跳转至

後綴數組簡介

一些約定

字符串相關的定義請參考 字符串基礎。

字符串下標從 \(1\) 開始。

字符串 \(s\) 的長度為 \(n\)。

" 後綴 \(i\)" 代指以第 \(i\) 個字符開頭的後綴，存儲時用 \(i\) 代表字符串 \(s\) 的後綴 \(s[i\dots n]\)。

後綴數組是什麼？

後綴數組（Suffix Array）主要關係到兩個數組：\(sa\) 和 \(rk\)。

其中，\(sa[i]\) 表示將所有後綴排序後第 \(i\) 小的後綴的編號，也是所説的後綴數組，後文也稱編號數組 \(sa\)；

\(rk[i]\) 表示後綴 \(i\) 的排名，是重要的輔助數組，後文也稱排名數組 \(rk\)。

這兩個數組滿足性質：\(sa[rk[i]]=rk[sa[i]]=i\)。

解釋

後綴數組示例：

後綴數組怎麼求？

O(n^2logn) 做法

相信這個做法大家還是能自己想到的：將盛有全部後綴字符串的數組進行 sort 排序，由於排序進行 \(O(n\log n)\) 次字符串比較，每次字符串比較要 \(O(n)\) 次字符比較，所以這個排序是 \(O(n^2\log n)\) 的時間複雜度。

O(nlog^2n) 做法

這個做法要用到倍增的思想。

首先對字符串 \(s\) 的所有長度為 \(1\) 的子串，即每個字符進行排序，得到排序後的編號數組 \(sa_1\) 和排名數組 \(rk_1\)。

倍增過程：

  1. 用兩個長度為 \(1\) 的子串的排名，即 \(rk_1[i]\) 和 \(rk_1[i+1]\)，作為排序的第一第二關鍵字，就可以對字符串 \(s\) 的每個長度為 \(2\) 的子串：\(\{s[i\dots \min(i+1, n)]\ |\ i \in [1,\ n]\}\) 進行排序，得到 \(sa_2\) 和 \(rk_2\)；

  2. 之後用兩個長度為 \(2\) 的子串的排名，即 \(rk_2[i]\) 和 \(rk_2[i+2]\)，作為排序的第一第二關鍵字，就可以對字符串 \(s\) 的每個長度為 \(4\) 的子串：\(\{s[i\dots \min(i+3, n)]\ |\ i \in [1,\ n]\}\) 進行排序，得到 \(sa_4\) 和 \(rk_4\)；

  3. 以此倍增，用長度為 \(w/2\) 的子串的排名，即 \(rk_{w/2}[i]\) 和 \(rk_{w/2}[i+w/2]\)，作為排序的第一第二關鍵字，就可以對字符串 \(s\) 的每個長度為 \(w\) 的子串 \(s[i\dots \min(i+w-1,\ n)]\) 進行排序，得到 \(sa_w\) 和 \(rk_w\)。其中，類似字母序排序規則，當 \(i+w>n\) 時，\(rk_w[i+w]\) 視為無窮小；

  4. \(rk_w[i]\) 即是子串 \(s[i\dots i + w - 1]\) 的排名，這樣當 \(w \geqslant n\) 時，得到的編號數組 \(sa_w\)，也就是我們需要的後綴數組。

過程

倍增排序示意圖：

顯然倍增的過程是 \(O(\log n)\)，而每次倍增用 sort 對子串進行排序是 \(O(n\log n)\)，而每次子串的比較花費 \(2\) 次字符比較；

除此之外，每次倍增在 sort 排序完後，還有額外的 \(O(n)\) 時間複雜度的，更新 \(rk\) 的操作，但是相對於 \(O(n\log n)\) 被忽略不計；

所以這個算法的時間複雜度就是 \(O(n\log^2n)\)。

實現 
 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1000010;

char s[N];
int n, w, sa[N], rk[N << 1], oldrk[N << 1];

// 為了防止訪問 rk[i+w] 導致數組越界，開兩倍數組。
// 當然也可以在訪問前判斷是否越界，但直接開兩倍數組方便一些。

int main() {
  int i, p;

  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (i = 1; i <= n; ++i) sa[i] = i, rk[i] = s[i];

  for (w = 1; w < n; w <<= 1) {
    sort(sa + 1, sa + n + 1, [](int x, int y) {
      return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];
    });  // 這裏用到了 lambda
    memcpy(oldrk, rk, sizeof(rk));
    // 由於計算 rk 的時候原來的 rk 會被覆蓋，要先複製一份
    for (p = 0, i = 1; i <= n; ++i) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
          oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {
        rk[sa[i]] = p;
      } else {
        rk[sa[i]] = ++p;
      }  // 若兩個子串相同，它們對應的 rk 也需要相同，所以要去重
    }
  }

  for (i = 1; i <= n; ++i) printf("%d ", sa[i]);

  return 0;
}

O(nlogn) 做法

在剛剛的 \(O(n\log^2n)\) 做法中，單次排序是 \(O(n\log n)\) 的，如果能 \(O(n)\) 排序，就能 \(O(n\log n)\) 計算後綴數組了。

前置知識：計數排序，基數排序。

由於計算後綴數組的過程中排序的關鍵字是排名，值域為 \(O(n)\)，並且是一個雙關鍵字的排序，可以使用基數排序優化至 \(O(n)\)。

實現 
 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1000010;

char s[N];
int n, sa[N], rk[N << 1], oldrk[N << 1], id[N], cnt[N];

int main() {
  int i, m, p, w;

  scanf("%s", s + 1);
  n = strlen(s + 1);
  m = 127;
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
  memcpy(oldrk + 1, rk + 1, n * sizeof(int));
  for (p = 0, i = 1; i <= n; ++i) {
    if (oldrk[sa[i]] == oldrk[sa[i - 1]]) {
      rk[sa[i]] = p;
    } else {
      rk[sa[i]] = ++p;
    }
  }

  for (w = 1; w < n; w <<= 1, m = n) {
    // 對第二關鍵字：id[i] + w進行計數排序
    memset(cnt, 0, sizeof(cnt));
    memcpy(id + 1, sa + 1,
           n * sizeof(int));  // id保存一份兒sa的拷貝，實質上就相當於oldsa
    for (i = 1; i <= n; ++i) ++cnt[rk[id[i] + w]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[id[i] + w]]--] = id[i];

    // 對第一關鍵字：id[i]進行計數排序
    memset(cnt, 0, sizeof(cnt));
    memcpy(id + 1, sa + 1, n * sizeof(int));
    for (i = 1; i <= n; ++i) ++cnt[rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[id[i]]]--] = id[i];

    memcpy(oldrk + 1, rk + 1, n * sizeof(int));
    for (p = 0, i = 1; i <= n; ++i) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
          oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {
        rk[sa[i]] = p;
      } else {
        rk[sa[i]] = ++p;
      }
    }
  }

  for (i = 1; i <= n; ++i) printf("%d ", sa[i]);

  return 0;
}

一些常數優化

如果你把上面那份代碼交到 LOJ #111: 後綴排序 上：

這是因為，上面那份代碼的常數的確很大。

第二關鍵字無需計數排序

思考一下第二關鍵字排序的實質，其實就是把超出字符串範圍（即 \(sa[i] + w > n\)）的 \(sa[i]\) 放到 \(sa\) 數組頭部，然後把剩下的依原順序放入：

1
2
3
4
5
for (p = 0, i = n; i > n - w; --i) id[++p] = i;

for (i = 1; i <= n; ++i) {
  if (sa[i] > w) id[++p] = sa[i] - w;
}

優化計數排序的值域

每次對 \(rk\) 進行更新之後，我們都計算了一個 \(p\)，這個 \(p\) 即是 \(rk\) 的值域，將值域改成它即可。

將 rk[id[i]] 存下來，減少不連續內存訪問

這個優化在數據範圍較大時效果非常明顯。

用函數 cmp 來計算是否重複

同樣是減少不連續內存訪問，在數據範圍較大時效果比較明顯。

把 oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]

替換成 cmp(sa[i], sa[i - 1], w)，

bool cmp(int x, int y, int w) { return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w]; }。

若排名都不相同可直接生成後綴數組

考慮新的 \(rk\) 數組，若其值域為 \([1,n]\) 那麼每個排名都不同，此時無需再排序。

實現 
 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1000010;

char s[N];
// key1[i] = rk[id[i]]（作為基數排序的第一關鍵字數組）
int n, sa[N], rk[N], oldrk[N << 1], id[N], key1[N], cnt[N];

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  int i, m = 127, p, w;

  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1;; w <<= 1, m = p) {  // m=p 就是優化計數排序值域
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;

    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
    // 注意這裏px[i] != i，因為rk沒有更新，是上一輪的排名數組

    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[key1[i]]--] = id[i];
    memcpy(oldrk + 1, rk + 1, n * sizeof(int));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    if (p == n) {
      break;
    }
  }

  for (i = 1; i <= n; ++i) printf("%d ", sa[i]);

  return 0;
}

O(n) 做法

在一般的題目中，常數較小的倍增求後綴數組是完全夠用的，求後綴數組以外的部分也經常有 \(O(n\log n)\) 的複雜度，倍增求解後綴數組不會成為瓶頸。

但如果遇到特殊題目、時限較緊的題目，或者是你想追求更短的用時，就需要學習 \(O(n)\) 求後綴數組的方法。

SA-IS

可以參考 誘導排序與 SA-IS 算法，另外它的 評論頁面 也有參考價值。

DC3

可以參考[2009] 後綴數組——處理字符串的有力工具 by. 羅穗騫。

後綴數組的應用

尋找最小的循環移動位置

將字符串 \(S\) 複製一份變成 \(SS\) 就轉化成了後綴排序問題。

例題：「JSOI2007」字符加密。

在字符串中找子串

任務是在線地在主串 \(T\) 中尋找模式串 \(S\)。在線的意思是，我們已經預先知道知道主串 \(T\)，但是當且僅當詢問時才知道模式串 \(S\)。我們可以先構造出 \(T\) 的後綴數組，然後查找子串 \(S\)。若子串 \(S\) 在 \(T\) 中出現，它必定是 \(T\) 的一些後綴的前綴。因為我們已經將所有後綴排序了，我們可以通過在 \(p\) 數組中二分 \(S\) 來實現。比較子串 \(S\) 和當前後綴的時間複雜度為 \(O(|S|)\)，因此找子串的時間複雜度為 \(O(|S|\log |T|)\)。注意，如果該子串在 \(T\) 中出現了多次，每次出現都是在 \(p\) 數組中相鄰的。因此出現次數可以通過再次二分找到，輸出每次出現的位置也很輕鬆。

從字符串首尾取字符最小化字典序

例題：「USACO07DEC」Best Cow Line。

題意：給你一個字符串，每次從首或尾取一個字符組成字符串，問所有能夠組成的字符串中字典序最小的一個。

題解

暴力做法就是每次最壞 \(O(n)\) 地判斷當前應該取首還是尾（即比較取首得到的字符串與取尾得到的反串的大小），只需優化這一判斷過程即可。

由於需要在原串後綴與反串後綴構成的集合內比較大小，可以將反串拼接在原串後，並在中間加上一個沒出現過的字符（如 #，代碼中可以直接使用空字符），求後綴數組，即可 \(O(1)\) 完成這一判斷。

參考代碼 
 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
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1000010;

char s[N];
int n, sa[N], id[N], oldrk[N * 2], rk[N * 2], px[N], cnt[N];

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  int i, w, m = 200, p, l = 1, r, tot = 0;

  cin >> n;
  r = n;

  for (i = 1; i <= n; ++i)
    while (!isalpha(s[i] = getchar()))
      ;
  for (i = 1; i <= n; ++i)
    rk[i] = rk[2 * n + 2 - i] = s[i];  // 拼接正反两个字符串，中间空出一个字符

  n = 2 * n + 1;
  // 求后缀数组
  for (i = 1; i <= n; ++i) ++cnt[rk[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w *= 2, m = p) {  // m=p 就是优化计数排序值域
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  // 利用后缀数组O(1)进行判断
  while (l <= r) {
    printf("%c", rk[l] < rk[n + 1 - r] ? s[l++] : s[r--]);
    if ((++tot) % 80 == 0) puts("");  // 回车
  }

  return 0;
}

height 數組

LCP（最長公共前綴）

兩個字符串 \(S\) 和 \(T\) 的 LCP 就是最大的 \(x\)(\(x\le \min(|S|, |T|)\)) 使得 \(S_i=T_i\ (\forall\ 1\le i\le x)\)。

下文中以 \(lcp(i,j)\) 表示後綴 \(i\) 和後綴 \(j\) 的最長公共前綴（的長度）。

height 數組的定義

\(height[i]=lcp(sa[i],sa[i-1])\)，即第 \(i\) 名的後綴與它前一名的後綴的最長公共前綴。

\(height[1]\) 可以視作 \(0\)。

O(n) 求 height 數組需要的一個引理

\(height[rk[i]]\ge height[rk[i-1]]-1\)

證明

當 \(height[rk[i-1]]\le1\) 時，上式顯然成立（右邊小於等於 \(0\)）。

當 \(height[rk[i-1]]>1\) 時：

根據 \(height\) 定義，有 \(lcp(sa[rk[i-1]], sa[rk[i-1]-1]) = height[rk[i-1]] > 1\)。

既然後綴 \(i-1\) 和後綴 \(sa[rk[i-1]-1]\) 有長度為 \(height[rk[i-1]]\) 的最長公共前綴，

那麼不妨用 \(aA\) 來表示這個最長公共前綴。（其中 \(a\) 是一個字符，\(A\) 是長度為 \(height[rk[i-1]]-1\) 的字符串，非空）

那麼後綴 \(i-1\) 可以表示為 \(aAD\)，後綴 \(sa[rk[i-1]-1]\) 可以表示為 \(aAB\)。（\(B < D\)，\(B\) 可能為空串，\(D\) 非空）

進一步地，後綴 \(i\) 可以表示為 \(AD\)，存在後綴（\(sa[rk[i-1]-1]+1\)）\(AB\)。

因為後綴 \(sa[rk[i]-1]\) 在大小關係的排名上僅比後綴 \(sa[rk[i]]\) 也就是後綴 \(i\)，小一位，而 \(AB < AD\)。

所以 \(AB \leqslant\) 後綴 \(sa[rk[i]-1] < AD\)，顯然後綴 \(i\) 和後綴 \(sa[rk[i]-1]\) 有公共前綴 \(A\)。

於是就可以得出 \(lcp(i,sa[rk[i]-1])\) 至少是 \(height[rk[i-1]]-1\)，也即 \(height[rk[i]]\ge height[rk[i-1]]-1\)。

O(n) 求 height 數組的代碼實現

利用上面這個引理暴力求即可：

1
2
3
4
5
6
for (i = 1, k = 0; i <= n; ++i) {
  if (rk[i] == 0) continue;
  if (k) --k;
  while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
  height[rk[i]] = k;
}

\(k\) 不會超過 \(n\)，最多減 \(n\) 次，所以最多加 \(2n\) 次，總複雜度就是 \(O(n)\)。

height 數組的應用

兩子串最長公共前綴

\(lcp(sa[i],sa[j])=\min\{height[i+1..j]\}\)

感性理解：如果 \(height\) 一直大於某個數，前這麼多位就一直沒變過；反之，由於後綴已經排好序了，不可能變了之後變回來。

嚴格證明可以參考[2004] 後綴數組 by. 徐智磊。

有了這個定理，求兩子串最長公共前綴就轉化為了 RMQ 問題。

比較一個字符串的兩個子串的大小關係

假設需要比較的是 \(A=S[a..b]\) 和 \(B=S[c..d]\) 的大小關係。

若 \(lcp(a, c)\ge\min(|A|, |B|)\)，\(A<B\iff |A|<|B|\)。

否則，\(A<B\iff rk[a]< rk[c]\)。

不同子串的數目

子串就是後綴的前綴，所以可以枚舉每個後綴，計算前綴總數，再減掉重複。

「前綴總數」其實就是子串個數，為 \(n(n+1)/2\)。

如果按後綴排序的順序枚舉後綴，每次新增的子串就是除了與上一個後綴的 LCP 剩下的前綴。這些前綴一定是新增的，否則會破壞 \(lcp(sa[i],sa[j])=\min\{height[i+1..j]\}\) 的性質。只有這些前綴是新增的，因為 LCP 部分在枚舉上一個前綴時計算過了。

所以答案為：

\(\frac{n(n+1)}{2}-\sum\limits_{i=2}^nheight[i]\)

出現至少 k 次的子串的最大長度

例題：「USACO06DEC」Milk Patterns。

題解

出現至少 \(k\) 次意味着後綴排序後有至少連續 \(k\) 個後綴以這個子串作為公共前綴。

所以，求出每相鄰 \(k-1\) 個 \(height\) 的最小值，再求這些最小值的最大值就是答案。

可以使用單調隊列 \(O(n)\) 解決，但使用其它方式也足以 AC。

參考代碼 
 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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>

using namespace std;

const int N = 40010;

int n, k, a[N], sa[N], rk[N], oldrk[N], id[N], px[N], cnt[1000010], ht[N], ans;
multiset<int> t;  // multiset 是最好写的实现方式

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  int i, j, w, p, m = 1000000;

  scanf("%d%d", &n, &k);
  --k;

  for (i = 1; i <= n; ++i) scanf("%d", a + i);  // 求后缀数组
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = a[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w <<= 1, m = p) {
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }

  for (i = 1, j = 0; i <= n; ++i) {  // 求 height
    if (j) --j;
    while (a[i + j] == a[sa[rk[i] - 1] + j]) ++j;
    ht[rk[i]] = j;
  }

  for (i = 1; i <= n; ++i) {  // 求所有最小值的最大值
    t.insert(ht[i]);
    if (i > k) t.erase(t.find(ht[i - k]));
    ans = max(ans, *t.begin());
  }

  cout << ans;

  return 0;
}

是否有某字符串在文本串中至少不重疊地出現了兩次

可以二分目標串的長度 \(|s|\)，將 \(h\) 數組劃分成若干個連續 LCP 大於等於 \(|s|\) 的段，利用 RMQ 對每個段求其中出現的數中最大和最小的下標，若這兩個下標的距離滿足條件，則一定有長度為 \(|s|\) 的字符串不重疊地出現了兩次。

連續的若干個相同子串

我們可以枚舉連續串的長度 \(|s|\)，按照 \(|s|\) 對整個串進行分塊，對相鄰兩塊的塊首進行 LCP 與 LCS 查詢，具體可見[2009] 後綴數組——處理字符串的有力工具。

例題：「NOI2016」優秀的拆分。

結合並查集

某些題目求解時要求你將後綴數組劃分成若干個連續 LCP 長度大於等於某一值的段，亦即將 \(h\) 數組劃分成若干個連續最小值大於等於某一值的段並統計每一段的答案。如果有多次詢問，我們可以將詢問離線。觀察到當給定值單調遞減的時候，滿足條件的區間個數總是越來越少，而新區間都是兩個或多個原區間相連所得，且新區間中不包含在原區間內的部分的 \(h\) 值都為減少到的這個值。我們只需要維護一個並查集，每次合併相鄰的兩個區間，並維護統計信息即可。

經典題目：「NOI2015」品酒大會

結合線段樹

某些題目讓你求滿足條件的前若干個數，而這些數又在後綴排序中的一個區間內。這時我們可以用歸併排序的性質來合併兩個結點的信息，利用線段樹維護和查詢區間答案。

結合單調棧

例題：「AHOI2013」差異

題解

被加數的前兩項很好處理，為 \(n(n-1)(n+1)/2\)（每個後綴都出現了 \(n-1\) 次，後綴總長是 \(n(n+1)/2\)），關鍵是最後一項，即後綴的兩兩 LCP。

我們知道 \(lcp(i,j)=k\) 等價於 \(\min\{height[i+1..j]\}=k\)。所以，可以把 \(lcp(i,j)\) 記作 \(\min\{x|i+1\le x\le j, height[x]=lcp(i,j)\}\) 對答案的貢獻。

考慮每個位置對答案的貢獻是哪些後綴的 LCP，其實就是從它開始向左若干個連續的 \(height\) 大於它的後綴中選一個，再從向右若干個連續的 \(height\) 不小於它的後綴中選一個。這個東西可以用 單調棧 計算。

單調棧部分類似於 Luogu P2659 美麗的序列 以及 懸線法。

參考代碼 
 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
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 500010;

char s[N];
int n, sa[N], rk[N << 1], oldrk[N << 1], id[N], px[N], cnt[N], ht[N], sta[N],
    top, l[N];
long long ans;

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  int i, k, w, p, m = 300;

  scanf("%s", s + 1);
  n = strlen(s + 1);
  ans = 1ll * n * (n - 1) * (n + 1) / 2;
  // 求后缀数组
  for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w <<= 1, m = p) {
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  // 求 height
  for (i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
    ht[rk[i]] = k;
  }
  // 维护单调栈
  for (i = 1; i <= n; ++i) {
    while (ht[sta[top]] > ht[i]) --top;  // top类似于一个指针
    l[i] = i - sta[top];
    sta[++top] = i;
  }
  // 最后利用单调栈算 ans
  sta[++top] = n + 1;
  ht[n + 1] = -1;
  for (i = n; i >= 1; --i) {
    while (ht[sta[top]] >= ht[i]) --top;
    ans -= 2ll * ht[i] * l[i] * (sta[top] - i);
    sta[++top] = i;
  }

  cout << ans;

  return 0;
}

類似的題目：「HAOI2016」找相同字符。

習題

參考資料

本頁面中（4070a9b 引入的部分）主要譯自博文 Суффиксный массив 與其英文翻譯版 Suffix Array。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

論文：

  1. [2004] 後綴數組 by. 許智磊

  2. [2009] 後綴數組——處理字符串的有力工具 by. 羅穗騫

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用