后缀数组问题

解题思路

本题就是后缀数组的模板题，直接套模板求一下 $sa$ 数组和 $height$ 数组。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010;

int n, m; //字符串长度、不同字符数量
char s[N];
//sa[i] 表示排名第 i 的是第几个后缀
//x[i] 表示第 i 个后缀的第一关键字
//y[i] 表示第 i 个后缀的第二关键字
//c[i] 表示关键字为 i 的数的个数
//rk[i] 表示第 i 个后缀的排名
//height[i] 表示排名第 i 的后缀和排名第 i - 1 的后缀的最长公共前缀
int sa[N], x[N], y[N], c[N], rk[N], height[N];

void get_sa() //预处理 sa
{
    //将所有后缀按照首字母从小到大排序（基数排序）
    for(int i = 1; i <= n; i++) c[x[i] = s[i]]++; //记录每个关键字出现的次数
    for(int i = 2; i <= m; i++) c[i] += c[i - 1]; //求前缀和
    for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i; //为每个数安排位置

    //每一轮将后缀按照前 2k 个字符排序
    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;

        //再将所有后缀按照第一关键字排序（基数排序）
        for(int i = 1; i <= m; i++) c[i] = 0;
        for(int i = 1; i <= n; i++) c[x[i]]++;
        for(int i = 2; i <= m; i++) c[i] += c[i - 1];
        for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0; //y 数组清空，用于后面存储当前的第一关键字

        //将排序后的所有后缀再按照前 2k 个字符离散化
        swap(x, y);
        x[sa[1]] = 1, num = 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]) ? num : ++num;

        if(num == n) break; //如果 n 个后缀的排名都不同，说明已经排好序
        m = num; //更新不同字符的个数
    }
}

void get_height() //预处理 height
{
    for(int i = 1; i <= n; i++) rk[sa[i]] = i; //预处理 rk
    //预处理 height
    for(int i = 1, k = 0; i <= n; i++) //k 记录当前的 h[i]
    {
        if(rk[i] == 1) continue; //height[1] 默认为 0
        if(k) k--; //应该从 h[i - 1] - 1 开始枚举，也就是 k - 1
        int j = sa[rk[i] - 1]; //记录第 i 个后缀前一个排名的后缀
        //如果 i 和 j 的第 k 位相同，则最长公共前缀长度 + 1
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k; //height[rk[i]] = k
    }
}

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

    n = strlen(s + 1), m = 122; //最大字符 'z' 的 ASCII 码是 122
    get_sa(); //预处理 sa
    get_height(); //预处理 height

    for(int i = 1; i <= n; i++) printf("%d ", sa[i]);
    puts("");
    for(int i = 1; i <= n; i++) printf("%d ", height[i]);

    return 0;
}