后缀数组SA学习笔记

Posted on | In , , ,

后缀数组SA学习

概述

后缀数组SA顾名思义是通过对字符串后缀的处理，解决一类问题

定义

后缀：${\rm suffix}(i)$表示字符串 $s$ 从第 $i$ 个位置开始的后缀，即由 $s[i]$ ~ $s[n−1]$ 组成的子串。

后缀数组：${\rm SA}[\ ]$保存了对字符串 $s$ 的所有后缀排序后的结果。 ${\rm SA}[i]$表示第 $i$ 小的后缀在原串中的起始位置。

名次数组：${\rm rank}[\ ]$ ，按起始位置保存了每个后缀在 ${\rm SA}[\ ]$ 中的排名。 ${\rm rank}[i]$ 表示 ${\rm suffix}(i)$ 的排名，即
${\rm rank}[{\rm SA}[i]]=i$（第 $i$ 小的后缀的排名为 $i$ ）。

高度数组：${\rm height}[\ ]$，保存了后缀数组 ${\rm SA}[\ ]$ 相邻两个后缀的最长公共前缀$({\rm LCP})$
$$
{\rm height}[i] = \begin{cases} 0 & i = 0 \ {\rm LCP}({\rm suffix}({\rm SA}[i]), {\rm suffix}({\rm SA}[i - 1])) & i > 0 \ \end{cases}
$$

即 $ {\rm height}[i] $ 表示存在的最大的 $ x $，满足对于任何 $ k \in [0, x) $ 有 $ s[{\rm SA}[i] + k] = s[{\rm SA}[i - 1] + k] $。
值得注意的是，$ {\rm height}[0] $ 的值是无效的，因为排名最靠前的后缀没有前一名。

原理

见Menci blog

模板

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
// 字符串输入从0开始
// hs[]:  用于后缀数组的字符串,有效位置为[hs,hs+len-1]
// sa[i]: 表示后缀第i小的起始位置
// rk[i]: suffix(i)的排名(排名为1的最小) 
// ht[i]: 后缀排名为i和i-1的最长公共后缀，即LCP(suffix(sa[i]), suffix(sa[i-1])) (i>0) 有效的i[1,len]

const int MAXN = 200000+7;
char hs[MAXN];
int sa[MAXN], rk[MAXN], ht[MAXN];

char ans[MAXN];

inline void suffixArray(int len) {
    int n=len;
    static int seet[MAXN], a[MAXN];
    for (int i = 0; i < n; i++) seet[i] = hs[i];
    sort(seet, seet + n);
    int *eend = unique(seet, seet + n);
    for (int i = 0; i < n; i++) a[i] = lower_bound(seet, eend, hs[i]) - seet;

    static int fir[MAXN], sec[MAXN], tmp[MAXN], _buc[MAXN + 1], *buc = _buc + 1;
    for (int i = 0; i < n; i++) buc[a[i]]++;
    for (int i = 0; i < n; i++) buc[i] += buc[i - 1];
    for (int i = 0; i < n; i++) rk[i] = buc[a[i] - 1];

    for (int t = 1; t < n; t *= 2) {
        for (int i = 0; i < n; i++) fir[i] = rk[i], sec[i] = i + t >= n ? -1 : rk[i + t];

        std::fill(buc - 1, buc + n, 0);
        for (int i = 0; i < n; i++) buc[sec[i]]++;
        for (int i = 0; i < n; i++) buc[i] += buc[i - 1];

        for (int i = 0; i < n; i++) tmp[n - buc[sec[i]]--] = i;

        std::fill(buc - 1, buc + n, 0);
        for (int i = 0; i < n; i++) buc[fir[i]]++;
        for (int i = 0; i < n; i++) buc[i] += buc[i - 1];

        for (int i = 0; i < n; i++) sa[--buc[fir[tmp[i]]]] = tmp[i];

        for (int i = 0; i < n; i++) {
            if (!i) rk[sa[i]] = 0;
            else if (fir[sa[i]] == fir[sa[i - 1]] && sec[sa[i]] == sec[sa[i - 1]]) rk[sa[i]] = rk[sa[i - 1]];
            else rk[sa[i]] = rk[sa[i - 1]] + 1;
        }
    }
    for (int i = 0, j, k = 0; i < n; i++) {
        if (!rk[i]) continue;
        j = sa[rk[i] - 1];
        if (k) k--;
        while (i + k < n && j + k < n && hs[i + k] == hs[j + k]) k++;
        ht[rk[i]] = k;
    }
}

上面大部分来自Menci blog suffix-array-notes