后缀数组（SA）

· · 算法·理论

目标

将给定字符串 s 的所有后缀排序。

做法 1

sort+暴力匹配判断，复杂度 O(n^2logn)

做法 2

sort+二分哈希判断，复杂度 O(nlog^2n)，但带着 hash 的大常数。

做法 3（后缀数组）

不会 DC3。只能用倍增求了。

定义 rk[i] 表示以位置 i 开始的后缀（s[i~n]），排完序后，排第几名。定义 sa[i] 表示排完序后，排名为 i 的后缀在原串中的开始位置是 sa[i]。因此不难有 sa[rk[i]] = i。

定义 height[i] 表示排名为 i 和排名为 i-1 的两个后缀的 LCP。

rk 数组的具体求法

倍增法。先把只考虑一个字符的排好序。设当前已经排好了长度为 len 的所有子串，尝试根据二元组 {rk[i], rk[i+len]} 来将所有长度为 2*len 的子串排序（其实就是先比前半段，再比后半段）。具体排序的时候需要用基数排序才能做到 O(n)。

sa 数组的具体求法

根据等式 sa[rk[i]] = i 即可。

height 数组的具体求法

很显然可以万能二分+hash 做到 O(nlogn)。但是能不能 O(n) 呢？

证明见 oi-wiki

根据这个东西，我们只要按照 rk 的顺序来求 height，不难发现均摊是 O(n) 的。

code：

const int N = 1000010;

int n, rk[N], sa[N], height[N], cnt[N];
// rk[i] 表示以位置i开始的后缀 排完序后 排第几名
// sa[i] 表示排完序后 排名为i的后缀在原串中的开始位置是sa[i]
// height[i] 表示排名为i和排名为i-1的两个后缀的LCP
char s[N];
struct node {
    int r[2], pos;
} z[N], zp[N];

void count_sort(int n, int m) { // 基数排序 O(n)
    G(j, 1, 0) {
        memset(cnt, 0, sizeof cnt);
        F(i, 1, n) cnt[z[i].r[j]]++;
        F(i, 1, m) cnt[i] += cnt[i-1];
        G(i, n, 1) zp[cnt[z[i].r[j]]--] = z[i];
        F(i, 1, n) z[i] = zp[i];
    }
    int tot = 0;
    rk[z[1].pos] = ++tot;
    F(i, 2, n) {
        if (z[i].r[0] == z[i-1].r[0] && z[i].r[1] == z[i-1].r[1]) rk[z[i].pos] = tot;
        else rk[z[i].pos] = ++tot;
    }
}

void get_sa(int n) {
    F(i, 1, n) z[i] = {{s[i], 0}, i};
    count_sort(n, 200); // 仅考虑第一个字符的排序
    for (int len = 1; len < n; len <<= 1) { // 当前已经处理好了所有长度为 len 的字符串
        F(i, 1, n) z[i] = {{rk[i], (i+len<=n?rk[i+len]:0)}, i}; // 算出长度为 2*len 的字符串的二元组
        count_sort(n, n);
    }
    F(i, 1, n) sa[rk[i]] = i;
}

void get_height(int n) {
    int k = 0;
    F(i, 1, n) {
        if (rk[i] == 1) continue;
        if (k) k--;
        int j = sa[rk[i]-1];
        while (i+k <= n && j+k <= n && s[i+k] == s[j+k]) k++;
        height[rk[i]] = k;
    }
}

void mymain() {
    scanf("%s", s+1);
    n = strlen(s+1);
    get_sa(n);
    get_height(n);
    F(i, 1, n) {
        printf("%d ", sa[i]);
    }
    puts("");
}