您现在的位置是:首页 >学无止境 >后缀树组 哈希+二分做法网站首页学无止境

后缀树组 哈希+二分做法

爱学习的图灵机 2024-06-14 17:20:13
简介后缀树组 哈希+二分做法

题目链接:

P4394 - 后缀数组

140. 后缀数组

题目描述

后缀数组 (SA) 是一种重要的数据结构,通常使用倍增或者 DC3 算法实现,这超出了我们的讨论范围。

在本题中,我们希望使用快排、Hash 与二分实现一个简单的 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) 的后缀数组求法。

详细地说,给定一个长度为 n n n 的字符串 S S S(下标 0 ∼ n − 1 0 sim n-1 0n1),我们可以用整数 k k k( 0 ≤ k < n 0 le k < n 0k<n) 表示字符串 S S S 的后缀 S ( k ∼ n − 1 ) S(k sim n-1) S(kn1)

把字符串 S S S 的所有后缀按照字典序排列,排名为 i i i 的后缀记为 S A [ i ] SA[i] SA[i]

额外地,我们考虑排名为 i i i 的后缀与排名为 i − 1 i-1 i1 的后缀,把二者的最长公共前缀的长度记为 H e i g h t [ i ] Height[i] Height[i]

我们的任务就是求出 S A SA SA H e i g h t Height Height 这两个数组。

输入格式

输入一个字符串,其长度不超过 30 30 30 万。

字符串由小写字母构成。

输出格式

第一行为数组 S A SA SA,相邻两个整数用 1 1 1 个空格隔开。

第二行为数组 H e i g h t Height Height,相邻两个整数用 1 1 1 个空格隔开,我们规定 H e i g h t [ 1 ] = 0 Height[1]=0 Height[1]=0

输入样例:

ponoiiipoi

输出样例:

9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

算法

1 计算哈希值和幂

首先,我们计算字符串 S S S 的每个前缀的哈希值 h [ i ] h[i] h[i],以及 b a s e base base 的各个幂 p [ i ] p[i] p[i]。这两个数组将在后续的步骤中用于加速排序和计算最长公共前缀。

2 构造后缀数组 SA

我们创建一个后缀数组 s a sa sa,其初始值为下标值。 s a sa sa 数组值(假设是 v v v)的含义是 s [ v : n ] s[v:n] s[v:n] 这一段子串。

然后对其进行排序,排序的规则是根据后缀的字典序进行排序。排序过程中,我们使用了哈希和二分搜索的方式来加速排序。

我们定义了一个比较函数 cmp,用于比较两个后缀的字典序大小。这个函数首先使用二分搜索的方式找到两个后缀的最长公共前缀,然后根据最长公共前缀后面的字符来确定后缀的字典序大小。

3 计算 Height 数组

Height 数组是表示后缀数组中相邻两个后缀的最长公共前缀的长度。我们可以直接使用前面求最长公共前缀的方法来求 Height 数组。

遍历 s a sa sa 数组,如果 i = 1 i = 1 i=1,输出 0;否则,输出 s a [ i ] sa[i] sa[i] s a [ i − 1 ] sa[i-1] sa[i1] 之间的最长公共前缀长度。

4 输出结果

最后,我们输出 SA 数组和 Height 数组。注意,题目要求输出从 0 开始的下标,所以在输出 SA 数组时需要将每个元素减 1。

时间复杂度

n n n 是字符串的长度,排序时间复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn),单次字典序比较 O ( log ⁡ n ) O(log n) O(logn),总时间复杂度 O ( n log ⁡ 2 n ) O(nlog^2n) O(nlog2n)

代码

// 爱学习的图灵机
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3e5 + 10, base = 131;
typedef unsigned long long ULL;

int n;
char s[N];
ULL h[N], p[N];
int sa[N];

ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

// 获取公共最长前缀长度,a和b为在s字符串中的起始位置
ULL getCommonPrefixLen(int a, int b){
    int l = 0, r = min(n - a, n - b) + 1;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(get(a, a + mid - 1) != get(b, b + mid - 1)) r = mid - 1;
        else l = mid;
    }
    return l;
}

// 比较两字符串字典序,a和b为在s字符串中的起始位置,含义是a位置之后的串和b位置之后的串
bool cmp(int a, int b){
    int len = getCommonPrefixLen(a, b);
    // 共同最长前缀长度len找到后,子串a~a+len-1 == 子串b~b+len-1
    // 所以a位置开头的串和b位置开头的串、向后数len位置的字符一定不同 a+len!=b+len
    // 比较这两个字符就是字典序比较。 
    // 如果a+len或b+len位置越界,则越界对应的字符串字典序更小。ab, abxxx..., ab字典序更小。
    // 由于越界位置为,越界对应的值一定小, 故无需额外判断。
    return s[a + len] < s[b + len];
}

int main(){
    scanf("%s", s + 1);    
    n = strlen(s + 1);
    p[0] = 1;
    
    for(int i = 1; i <= n; ++ i){
        sa[i] = i;
        h[i] = h[i - 1] * base + s[i];
        p[i] = p[i - 1] * base;
    }

    sort(sa + 1, sa + n + 1, cmp);
    
    for(int i = 1; i <= n; ++ i) printf("%d ", sa[i] - 1);
    puts("");
    for(int i = 1; i <= n; ++ i){
        if(i == 1) printf("0 ");
        else printf("%d ", getCommonPrefixLen(sa[i], sa[i - 1]));
    }
    
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。