CloudySky

纵使世界万般残酷

总有温暖值得守护

后缀数组 学习笔记

注：仅仅是为了以后的学习预习一下。应该会很草。大部分参考的 OI Wiki

在计算机科学里，后缀数组是一个通过对字符串的所有后缀经过排序后得到的数组。–百度百科

约定以 ii 为起始位置的后缀称为后缀 ii ，S(i)S(i) 表示后缀 ii 对应的字符串。

一般记后缀数组为 saisa_i 表示的排名为 ii 的后缀所对应的起始位置（显然不能直接把字符串存起来）。同时记 rkirk_i 表示后缀 ii 的排名。可知 sasa 和 rkrk 互为逆操作，构成双射关系，因此可知 sa[rk[i]]=isa[rk[i]] = i 。

还有一个 heightheight 数组，表示 saisa_i 对应后缀和 sai−1sa_{i - 1} 对应后缀的最长公共前缀（ lcplcp ）。即 heighti=lcp(sai,sai−1)height_i = lcp(sa_{i}, sa_{i - 1}) 它的性质：

  1. height[rk[i]]≥height[rk[i−1]]−1height[rk[i]] \ge height[rk[i - 1]] - 1

利用这个性质可以 O(n)O(n) 求 heightheight 数组。

证明：

令 aa 为一个字符，不同的大写字母表示不同的字符串。

当 height[rk[i−1]]>1height[rk[i - 1]] > 1 时：

设后缀 i−1i - 1 为 aABaAB （A 为长度为 height[rk[i−1]]−1height[rk[i - 1]] - 1 的字符串），则后缀 ii 为 ABAB 。

令 rk[i−1]=xrk[i - 1] = x ，heightx=lcp(sax,sax−1)height_x = lcp(sa_x, sa_{x - 1})

即 height[rk[i−1]]=lcp((sa[rk[i−1]]→i−1),sa[rk[i−1]−1])=aAheight[rk[i - 1]] = lcp((sa[rk[i - 1]] \to i - 1), sa[rk[i - 1] - 1]) = aA 。

且非常显然 (S(sa[rk[i−1]−1])→aAC)≤S(i−1)(S(sa[rk[i - 1] - 1]) \to aAC) \le S(i - 1) .

可以得出 (S(sa[rk[i−1]−1]+1)→AC)≤AB(S(sa[rk[i - 1] - 1] + 1) \to AC) \le AB .

(height[rk[i]]=lcp(sa[rk[i]],sa[rk[i−1]]))≥height[rk[i−1]]−1(height[rk[i]] = lcp(sa[rk[i]], sa[rk[i - 1]])) \ge height[rk[i - 1]] - 1 .

证毕。

  1. ∀x,y∈[1,∣S∣]&&x<y,lcp(x,y)=min⁡k=x+1y(hegihtk)\forall x, y \in[1, |S|]\&\& x < y, lcp(x, y) = \min_{k = x + 1} ^ y(hegiht_k)

利用这个性质可以将 lcplcp 问题转化为 RMQRMQ 问题。

  1. 不同子串的个数=n(n+1)2−∑i=2heighti\text{不同子串的个数} = \dfrac{n(n + 1)}{2} - \sum_{i = 2} height_i

具体实现：

倍增求 sasa 数组，同时求 rkrk 数组。考虑类似 STST 表的区间合并。

  • 设 saw[i]sa_w[i] 表示，长度为 ww 的所有子串中，以 ii 为起始位置的子串对应的排名。

  • 对每个字符进行排序，求 sa1sa_1 数组。

  • 设当前倍增长度为 ww ，根据字符串排序规则，直接以 saw[i+w]sa_w[i + w] 为第二关键字，以 saw[i]sa_w[i] 为第一关键字进行排序，即可求出 sa2w[i]sa_{2w}[i]。

    注：因为倍增本身复杂度为 O(logn)O(logn) ，如果使用普通的 sortsort 复杂度无法通过，因此采用时间复杂度 O(n)O(n) 计数排序。

  • 一些优化：

    1. 第二关键字无需真正排序。只需要先将 n→n−wn \to n - w 依次记录（空串字典序必然小），然后再从头开始扫，把 sa>wsa > w 的值依次记录。

      因为当前扫描以 ii 为起始位置的串要接在以 i−wi - w 为起始位置的串之后，所以只有这些串有意义，且在上一轮均已排好。

    2. 可以根据上次的 rkrk 修改值域。

利用 heightheight 数组的性质 11 线性求 heightheight 数组。

代码实现： 
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
// 后缀数组 学习笔记
bool cmp (int x, int y, int w) {
  return trk[x] == trk[y] && trk[x + w] == trk[y + w];
}

void SA (int n) {
  // 计数排序数组，cnt 为当前值所对应的个数， id 为按照第二关键字排号的序列。
  static int cnt[Maxn], id[Maxn];
  int m = 300, p;
  // 对字符的排序
  for (int i = 1; i <= n; ++i)
    ++cnt[rk[i] = s[i]];
  for (int i = 1; i <= m; ++i)
    cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i)
    sa[cnt[rk[i]]--] = i;
  for (int w = 1; ; w <<= 1, m = p) {
    // 将第二关键字排序（已优化）
    p = 0;
    for (int i = n; i > n - w; --i) id[++p] = i;
    for (int k = 1; k <= n; ++k)
      if (sa[k] > w) id[++p] = sa[k] - w;
    // 第一关键字排序
    memset (cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++i)
      ++cnt[rk[id[i]]];
    for (int i = 1; i <= m; ++i)
      cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i)
      sa[cnt[rk[id[i]]]--] = id[i];
    // 处理求 RK 数组，处理值域。
    memcpy (trk, rk, sizeof (rk));
    p = 0;
    for (int i = 1; i <= n; ++i)
      rk[sa[i]] = cmp (sa[i], sa[i - 1], w) ? p : ++p;
    // 收尾
    if (p == n) {
      for (int i = 1; i <= n; ++i)  sa[rk[i]] = i;
      break;
    }
  }
  for (int i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
    h[rk[i]] = k;
  }
}

本文作者：CloudySky
写作时间： 2022-01-14
最后更新时间： 2022-01-14
遵循协议： BY-NC-SA

Top