Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P3809 【【模板】后缀排序】

posted on 2019-08-28 09:49:06 | under 题解 |

后缀数组是一个思路较为清晰,代码十分玄学的操作,建议大家按照代码模拟一下样例,理解每一步操作的意义

后缀数组的作用是将长度为N的字符串的N个后缀来进行排序

我们直接排序的复杂度是 $O(N^2logN)$

后缀数组常用方法是倍增+基数排序算法:

1.基数排序

我们先来看一下代码:(默认升序排列)

//rep(i, a, b)是正序从a-b枚举
//drep(i, a, b)是倒序从a-b枚举
//a数组为基数排序辅助数组,即为一个桶
//rk数组为基数排序的第一关键字
//tp第二关键字中,排名为i的数的位置
//sa数组可以在此处理解为排完序后排名为i的数对的位置
il void Qsort() {
    rep(i, 1, m) a[i] = 0;//
    rep(i, 1, n) ++ a[rk[i]];
    rep(i, 1, m) a[i] += a[i - 1];
    //记录前缀和以后,a[i]的意义是rak为i的数最大可以到哪里
    drep(i, 1, n) sa[a[rk[tp[i]]] --] = tp[i];
    //-- a的意义是减少了一个位置,所以a最大可以到的位置往前移一个
}

我们来模拟一下,假设我们要对一个数组进行基数排序

其中第一关键字为: $1\ 3\ 2\ 1\ 4\ 3\ 1\ 2$

对应第二关键字为: $3\ 2\ 1\ 2\ 3\ 3\ 1\ 3$

所以对应 $tp$ 数组为: $3\ 7\ 2\ 4\ 1\ 5\ 6\ 8$

第一步

我们清空桶

第二步

我们将第一关键字压入桶中,得到a数组: $3\ 2\ 2\ 1$

第三步

我们将a数组记录前缀和,得到a数组: $3\ 5\ 7\ 8$

然后我们就可以发现一个奇妙的性质

对与第一关键字为1的数对,他们的排名为 $1-3$

对与第一关键字为2的数对,他们的排名为 $4-5$

对与第一关键字为3的数对,他们的排名为 $6-7$

对与第一关键字为4的数对,他们的排名为 $8-8$

所以从某种意义上来说,我们已经对第一关键字排好了序

第四步

我们从前往后倒序枚举

首先,最后一个数对的第二关键字为8,第8个数对的第一关键字为2,2的桶现在为5,所以排名为5的位置是第8个

然后2的桶减一,因为第五个位置已经被占用,所以第一关键字为2的数对排名为 $4-4$

第7个数对的第二关键字为6,第六个数的第一关键字的桶为7个,于是排名为7的位置是第6个

以此类推,我们可以拍好序,最后的sa数组为 $7\ 4\ 1\ 3\ 8\ 2\ 6\ 5$

2.倍增

定义:

$1.\ <a, b>$ 为以a为第一关键字,b为第二关键字进行基数排序) $2.\ s[i]$ 表示原数组的第i位字符

$3.\ i-$ 后缀表示对字符串S的每个后缀,取左边i个字符,得到一个i-后缀

$4.\ rk[i][j]$ 表示第j位上的i-后缀的排名

操作:

我们可以先按 $<i, s[i]>$ 进行基数排序,得到 $rk[1][i]$

再按照 $<rk[1][i], rk[1][i + 1]>$ 进行基数排序,得到 $rk[2][i]$

因为是倍增,所以我们可以通过 $<rk[2][i], rk[2][i + 2]>$ 进行基数排序,得到 $rk[4][i]$

同理,我们也可以用 $<rk[4][i], rk[4][i + 4]>$ 进行基数排序,得到 $rk[8][i]$

当所有 $rk[2^k][i]$ 互不相同,排序结束

代码如下(倍增部分代码有详细注释,就不模拟了,各位最好手动模拟,理解每一行代码,注意在模拟的时候分清楚rk[i]和sa[i]的区别,一定要先清楚每一个数组的意义!!!):

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
#define il inline
#define re register
#define debug printf("Now is Line : %d\n",__LINE__)
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
#define _ 1000005 
int n, m, a[_], sa[_], rk[_], tp[_];
char c[_];
/*
sa[i]:排名为i的后缀的位置
rk[i]:第i个位置开始的后缀的排名,作为基数排序的第一关键字
即sa[rk[i]] = rk[sa[i]] = i
tp[i]:第二关键字中,排名为i的数的位置
a[i]:有多少个元素排名为i
c[i]:原输入数组 
*/
il int get(char c) {
    if(c >= '0' && c <= '9') return c - '0' + 1;
    if(c >= 'A' && c <= 'Z') return c - 'A' + 11;
    return c - 'a' + 37;
}
il void init() {
    rep(i, 1, n) rk[i] = get(c[i]), tp[i] = i;
}
il void print() {
    rep(i, 1, n) printf("%d ", sa[i]);
}
il void Qsort() {
    rep(i, 1, m) a[i] = 0;
    rep(i, 1, n) ++ a[rk[i]];
    rep(i, 1, m) a[i] += a[i - 1];
    drep(i, 1, n) sa[a[rk[tp[i]]] --] = tp[i];
}
il void get_sort() {
    for(re int w = 1, p = 0; p < n && w <= n; m = p, p = 0, w <<= 1) {
        //p在此时的意义是最高出现的排名以及一个计数器 
        //p < n的意义是如果当前最大排名== n则无继续排序的意义 
        rep(i, n - w + 1, n) tp[++ p] = i;
        //这里p的定义只是一个计数器 
        //tp[i]表示第二关键字中,排名为i的数的位置
        //因为i - w + 1后面没有第二关键字,所以要补0 
        //所以要设成极小值排在前面
        rep(i, 1, n) if(sa[i] > w) tp[++ p] = sa[i] - w;
        //在第一关键字中排名越靠前,表示应该排在前面
        Qsort(), swap(rk, tp), p = rk[sa[1]] = 1;
        //我们现在更新rk,tp已经无用,先备份,用memcpy也行
        //注意到一个性质 : rk[sa[i]] = i
        rep(i, 2, n) rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++ p;
        //注意tp和rk已经交换,所以这个判断的意思是:
        //如果两个后缀还相等,则排名不变,否则++
    }
}
int main() {
    scanf("%s", c + 1), n = strlen(c + 1), m = 62;
    init(), Qsort(), get_sort(), print();
    return 0;
}