跳转至

后缀数组 (SA)

前言

后缀数组和后缀树

在字符串处理当中，后缀树和后缀数组都是非常有力的工具。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。——百度百科

各种定义

子串：就是子串。[捂脸]

后缀：就是从 i这个位置开始到该字符串的末尾的一个子串。

字符串大小比较：把 a和 b这两个串按照字典序进行比较。

字典序：从左到右比较，遇到第一个不相同的字符时，字符在字母表中靠前的字典序较小；若某个串已扫描完，而另一个串未扫描完，且前面的字符都相同，则已扫描完的字典序靠前（即设长度较短的为串 S_1，较长的为 S_2， S_2前 |S_1|个字符为 S_2'，且 S_2'=S_1，则 S_1字典序较小）；若两串长度相等且未找到不同的字符，则称两串相同）

后缀数组： sa[i]代表该字符串的 len个后缀中，从 sa[i]开始的后缀排在为 i个。 sa数组记录的是“排第几的是哪个后缀”。

名次数组： rank[i]代表从 i开始的后缀排名为 rank[i]。 rank数组记录的是“某个后缀排在第几个”。

一些构造方法

最简单的暴力

把所有的后缀拆出来，然后 sort。由于直接比较长度为 n的字符串的时间复杂度为 O(n)，所以整体时间复杂度为 O(n^2 \log 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
int rank[123], sa[123];

struct Str {
  string s;
  int wei;
  friend bool operator<(Str a1, Str a2) { return a1.s < a2.s; }
} k[123];

int main() {
  string s;
  cin >> s;
  int len = s.size() - 1;

  for (int i = 0; i <= len; i++) {
    k[i].wei = i;
    for (int j = i; j <= len; j++) k[i].s = k[i].s + s[j];
  }

  sort(k, k + len + 1);
  for (int i = 0; i <= len; i++) {
    rank[k[i].wei] = i;
    sa[i] = k[i].wei;
  }

  exit(0);
}

倍增法

这个就是一般写后缀数组用的方法，复杂度是 O(n\log n)，前提是你要先会 基数排序 。

假设我们有这样一个字符串 aabaaaab ，然后我们把所有的后缀列举出来：

然后用基数排序的方式，按照每个后缀的第一个字母进行排序，呈现这样子的效果：

接着我们以第二个字母为关键字，在首字母有序的基础上进行排序，这个时候，我们把首字母相同的后缀拿出来单看。

对于每一组首字母相同的后缀，首字母是对排序没有影响的，所以可以直接按照第二个字母进行基数排序，同样，对于首字母不同的后缀，由于按照首字母排序时，他们的相对大小已经确定，当按照第二个字母排序时，不会出现“原来 a>b，现在 b>a”的现象，所以我们可以看成一直在做区域内的排序，这之后变成这样：

第三字母同理……

这样子我们可以处理这个问题，可是复杂度还是没有到达一个我们可以接受的范围，所以我们引入 倍增 。

当我们按照每个后缀的前 2^k个字母进行完排序后，那么我们把后缀的前 2^{k+1}看做前后两个 2^k, 这样我们就可以把这前后两个 2^k作为之前说的首字母和第二个字母了，然后进行上述过程，就可以在 O(nlogn)的复杂度内处理这个问题了。

 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
#include <bits/stdc++.h>
using namespace std;

int n;
int sa[150], x[150], c[150], y[150];
char a[150];

inline void SA() {
  int m = 128;
  for (int i = 0; i <= m; i++) c[i] = 0;
  for (int i = 1; i <= n; i++) c[x[i]]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = n; i; i--) sa[c[x[i]]--] = i;

  for (int k = 1, p; k <= n; k <<= 1) {
    p = 0;
    for (int i = n; i > n - k; i--) y[++p] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > k) y[++p] = sa[i] - k;

    for (int i = 0; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[x[i]]++;
    for (int i = 1; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i; i--) sa[c[x[y[i]]]--] = y[i];

    p = y[sa[1]] = 1;
    for (int i = 2, a, b; i <= n; i++) {
      a = sa[i] + k > n ? -1 : x[sa[i] + k];
      b = sa[i - 1] + k > n ? -1 : x[sa[i - 1] + k];
      y[sa[i]] = (x[sa[i]] == x[sa[i - 1]]) && (a == b) ? p : ++p;
    }
    swap(x, y);
    m = p;
  }
}

int main() {
  scanf("%s", a + 1);

  n = strlen(a + 1);
  for (int i = 1; i <= n; i++) x[i] = a[i];
  SA();

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

代码里 x[i]就是 rank[i]。

y[i]：假设 y[i]=a\ ,\ y[i+1]=b那么在原串中从 a+2^k开始的 2^k个字符组成的子串 小于等于 从 b+2^k开始的 2^k个字符组成的子串。

最好理解这个代码时，每一步都结合这基数排序来考虑。

DC3

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

评论