AcWing 2715. 后缀数组

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 2715. 后缀数组原题链接中等

作者：

Equation_6 , 2025-03-24 20:11:52 ·山西 , 所有人可见 , 阅读 2

AcWing 2715. 后缀数组题解

题目分析

本题给定一个只包含大小写英文字母和数字的字符串，需要对字符串的(n)个非空后缀进行字典序排序，并求出两个数组(SA)和(Height)。(SA[i])记录排名为(i)的非空后缀的起始字符在字符串中的位置编号，(Height[i])记录排名为(i)的非空后缀与排名为(i - 1)的非空后缀的最长公共前缀的长度（(Height[1]=0)）。

解题思路

本题主要通过基数排序和倍增算法来构造后缀数组(SA)，然后根据后缀数组计算(Height)数组。
1. 基数排序用于对后缀进行初步排序，通过多轮排序逐步确定后缀的字典序顺序。
2. 倍增算法通过不断倍增后缀的长度，利用上一轮的排序结果进行下一轮排序，最终得到完整的后缀数组。
3. 在得到后缀数组后，通过一定的计算方式得出(Height)数组。

代码逐段分析

头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];

引入必要的头文件，iostream用于输入输出，cstring用于字符串操作，algorithm用于算法相关功能。
定义常量(N)表示字符串的最大长度。
变量(n)表示字符串的长度，(m)在基数排序中用于表示字符的种类数。
s[N]存储输入的字符串。
sa[N]存储后缀数组，sa[i]表示排名为(i)的后缀的起始位置。
x[N]和y[N]用于辅助排序，x[i]表示原字符串中第(i)个位置的字符在当前排序轮的排名，y[i]用于暂存下一轮排序的信息。
c[N]用于基数排序中的计数数组。
rk[N]是(sa)的逆数组，rk[i]表示起始位置为(i)的后缀的排名。
height[N]存储排名为(i)的后缀与排名为(i - 1)的后缀的最长公共前缀的长度。
构造后缀数组函数

void get_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; i -- ) sa[c[x[i]] -- ] = i;

第一轮基数排序：
- 统计每个字符出现的次数，将字符赋值给(x[i])并在(c)数组中计数。
- 计算前缀和，方便后续确定每个字符的排名位置。
- 根据计数结果，将字符位置放入(sa)数组中，完成第一轮排序。

    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;

倍增排序：
- 对于每一轮倍增（(k)从(1)开始每次翻倍）：
- 先将长度为(k)的后缀中，超出字符串长度(k)的部分的起始位置放入(y)数组。
- 再将其他满足条件（起始位置大于(k)）的后缀的起始位置 - (k)放入(y)数组，这样做是为了利用上一轮的排序结果。

        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; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;

再次进行基数排序：
- 重置计数数组(c)。
- 统计(x)数组中每个排名出现的次数。
- 计算前缀和。
- 根据(x[y[i]])的排名，将(y[i])对应的位置放入(sa)数组中，完成这一轮排序，并清空(y[i])。

        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;
        m = num;
    }
}

交换(x)和(y)数组，为下一轮排序做准备。
确定新的排名：如果两个后缀在当前长度(k)下的两部分（前(k)个字符和后(k)个字符）排名都相同，则它们的新排名也相同，否则新排名递增。
如果所有后缀的排名都不同（(num == n)），说明已经完成排序，退出循环。否则更新(m)为当前的排名种类数。
计算Height数组函数

void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;

首先根据后缀数组(sa)计算逆数组(rk)，方便后续计算(Height)数组。

    for (int i = 1, k = 0; i <= n; i ++ )
    {
        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;
    }
}

计算(Height)数组：
- 从第二个后缀开始（因为(Height[1]=0)）。
- 利用(k)来记录最长公共前缀的长度，每次先将(k)减(1)（可以利用上一个后缀的结果进行优化）。
- 找到排名为(rk[i] - 1)的后缀的起始位置(j)。
- 通过循环比较两个后缀的字符，更新(k)，并将(k)赋值给(height[rk[i]])。
主函数

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 122;
    get_sa();
    get_height();

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