天才和疯子互相为邻

后缀数组（SA）学习笔记

发表于 分类于

定义

将一个字符串的每个后缀按字典序排序，后缀数组 $ sa_i $ 表示排名为 $ i $ 的后缀的起始下标。

求法

将所有后缀快排，复杂度 $O(n^2\log n)$，太大。

正确做法为倍增+基数排序，复杂度 $O(n\log n)$。

首先比较每个后缀的第一个字符，得出第一关键字。

接着以第二个字符为第二关键字，注意这里我们存的是排名为 $i$ 的后缀的起始位置。

按照两个关键字排序，得到每个后缀的排名（可以并列），变为第一关键字。

接下来倍增，同时比较第三、四个字符，得出新的第二关键字。

注意到第三、四个字符的排名已经算好了，起始下标为 $i$ 的后缀，第三、四个字符的排名就是下表为 $i+2$ 的后缀的第一关键字。

如果没有三、四个字符，那么排名就最前（用 $0$ 表示）。

于是以此类推，每次比较到 $2^k$，直到排名互不相同，算法结束。

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
inline void gsa()
{
    for (int i = 1; i <= n; i++) {
        x[i] = a[i - 1];
        y[i] = i;
        m = max(m, x[i]);
    }
    ssort();
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; i++)
            y[++num] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                y[++num] = sa[i] - k;
        ssort();
        swap(x, y);
        x[sa[1]] = 1;
        num = 1;
        for (int i = 2; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
                x[sa[i]] = num;
            else
                x[sa[i]] = ++num;
        }
        if (num == n)
            break;
        m = n;
    }
    return;
}

基数排序

复杂度 $O(n)$ ，类似桶排。

我们先把第一关键字装进桶里，做一个前缀和，就能知道每个桶里的数排名的上界。第二关键字是升序排序的，前面的排名较高。于是我们倒序遍历，从小到大出来，排名的上界也不断减小，就能成功排完。

1
2
3
4
5
6
7
8
9
10
11
inline void ssort()
{
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i++)
        g[x[i]]++;
    for (int i = 1; i <= m; i++)
        g[i] += g[i - 1];
    for (int i = n; i >= 1; i--)
        sa[g[x[y[i]]]--] = y[i];
    return;
}

应用：（$LCP$）

显然除了模板题不可能出裸题。

因此我们需要利用一个叫 $LCP$ 的东西。

定义

两个字符串的最长公共前缀。

求法

这里我们需要一个数组 $height$，$height_i$ 即表示 $lcp(sa_i,sa_{i-1})$，即第 $i$ 名的后缀与它前一名的后缀的最长公共前缀。

一个引理：$height_{rk_i}\ge height_{rk_{i-1}}-1$。

其中 $rk_i$ 表示以 $i$ 为起始字符的后缀的排名。

利用这个引理，暴力就可以 $O(n)$ 求得 $height$。

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