后缀数组

原理

模板题

AcWing-140-后缀数组

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000010;
int n, m;
char str[N];
int x[N], y[N], c[N];
int sa[N], rk[N], height[N];

void get_suffix_array () {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++ i) ++ c[x[i] = str[i]];
    for (int i = 1; i <= m; ++ i) c[i] += c[i - 1];
    for (int i = n; i >= 1; -- i) sa[c[x[i]] --] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int cnt = 0;
        for (int i = n - k + 1; i <= n; ++ i) y[++ cnt] = i;
        for (int i = 1; i <= n; ++ i)
            if (sa[i] > k)
                y[++ cnt] = sa[i] - k;
        memset(c, 0, sizeof(c));
        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 >= 1; -- i) sa[c[x[y[i]]] --] = y[i];
        for (int i = 1; i <= n; ++ i) y[i] = x[i];
        x[sa[1]] = 1;
        cnt = 1;
        for (int i = 2; i <= n; ++ i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? cnt : ++ cnt);
        if (cnt == n) break;
        m = cnt;
    }
}
void get_height () {
    for (int i = 1; i <= n; ++ i) rk[sa[i]] = i;
    int k = 0;
    for (int i = 1; i <= n; ++ i) {
        if (rk[i] == 1) continue;
        if (k > 0) -- k;
        int j = sa[rk[i]- 1];
        while (str[i + k] == str[j + k]) ++ k;
        height[rk[i]] = k;
    }
}

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

    n = strlen(str + 1), m = 122;
    get_suffix_array();
    get_height();

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

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000010;
int n, m;
char str[N];
int x[N], y[N], c[N];
int sa[N], rk[N], height[N];

/*  后缀str[i ~ n]的位置(以下简称为"位置")
    = 后缀str[i ~ n]对应的二元组的位置(以下简称为"位置")
    = i

    升序排序, 第 1 名最小

    := 表示赋值, = 表示数值相等

    sa[排名] = 位置, rk[位置] = 排名
    sa[rk[i]] := i;// 已知rk求sa
    rk[sa[i]] := i;// 已知sa求rk

    x[位置] = 二元组的第一关键字
    y[(第二关键字的)排名] = 位置  */
void get_suffix_array () {
    // --------------- 计数排序 ---------------
    for (int i = 1; i <= n; ++ i) {
        x[i] = str[i];
        ++ c[x[i]];
    }
    for (int i = 1; i <= m; ++ i) c[i] += c[i - 1];
    for (int i = n; i >= 1; -- i) {
        sa[c[x[i]]] = i;
        -- c[x[i]];
    }

    // --------------- 倍增 ---------------
    for (int k = 1; k <= n; k <<= 1) {
        int cnt = 0; // 不相同后缀的个数

        /*  此时, 二元组为(第一关键字, 0(或者说不存在))
            sa[排名] = sa[(第一关键字的)排名] = 位置  */

        // --------------- 排序第二关键字 ---------------
        // 二元组[n-k+1 ~ n]的第二关键字 := 0
        for (int i = n - k + 1; i <= n; ++ i) y[++ cnt] = i;
        for (int i = 1; i <= n; ++ i) // 从小到大(⚠)枚举第一关键字
            if (sa[i] > k)
                y[++ cnt] = sa[i] - k;
        // 二元组[sa[i] - k]的第二关键字 := 二元组[sa[i]]的第一关键字

        // 此时, 二元组为(第一关键字, 第二关键字)

        // --------------- 计数排序 + 基数排序 ---------------
        memset(c, 0, sizeof(c));
        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 >= 1; -- i) { // 从大到小(⚠)枚举第二关键字
            sa[c[x[y[i]]]] = y[i];// 计算二元组的排名

            // 重点、难点
            // 在第一关键字相同的条件下, 第二关键字越大, 二元组的排名越大
            -- c[x[y[i]]];
        }

        // ---------- 二元组的第一关键字 := 二元组的排名 ----------
        for (int i = 1; i <= n; ++ i) y[i] = x[i];
        // y := 原第一关键字
        x[sa[1]] = 1;
        cnt = 1;
        for (int i = 2; i <= n; ++ i) { // 从小到大枚举排名
            // 判断二元组[sa[i]]和[sa[i - 1]]是否相同
            /*  为什么是y[sa[i] + k], 请参考上文的语句
                if(sa[i] > k)
                    y[++ cnt] = sa[i] - k;
            */
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
                x[sa[i]] = cnt;
            else
                x[sa[i]] = ++ cnt;
        }
        if (cnt == n) break;
        m = cnt;
    }
}
void get_height () {
    for (int i = 1; i <= n; ++ i) rk[sa[i]] = i; // 计算rk数组

    // h[i] = height[rk[i]] = lcp(rk[i], r[i] - 1)
    // 根据h[i] ≥ h[i - 1] - 1计算h数组. 同时, 求得了height数组
    int k = 0;
    for (int i = 1; i <= n; ++ i) { // 从小到大枚举位置
        if (rk[i] == 1) continue;
        if (k > 0) -- k; // 此时, k = h[i - 1] - 1
        int j = sa[rk[i]- 1]; // 字符串str[i ~ n]的前一名的位置
        while (str[i + k] == str[j + k]) ++ k;
        /*  朴素地匹配
            不怕数组的下标越界  */
        height[rk[i]] = k;
        /*  height[rk[i]]就是h[i]
            此时, k = h[i]  */
    }
}

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

    n = strlen(str + 1);
    m = 122;
    /*  max{ASCII('A'), ASCII('B'), ..., ASCII('z')}
        = ASCII('z')
        = 122
    */
    get_suffix_array();
    get_height();

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