P3809 【模板】后缀排序

题目链接：https://www.luogu.org/problemnew/show/P3809

题目背景

这是一道模板题。

题目描述

读入一个长度为 nn 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 11 到 nn。

输入输出格式

输入格式：

一行一个长度为 nn 的仅包含大小写英文字母或数字的字符串。

输出格式：

一行，共n个整数，表示答案。

输入输出样例

输入样例#1：

ababa

输出样例#1：

5 3 1 4 2

题解：

后缀数组模板题= =哇，后缀数组代码看了我好久，最终还是似懂非懂的，管他的，先用着/滑稽

其实我感觉后缀数组的思想还是比较好理解的，就是这个代码，基数排序那里有点迷，代码中有很多巧妙的细节吧，比如求前缀和后面倒着来求sa数组，我感觉这是最巧妙的地方了。

还有就是对第一、二关键字整体排序那里，倒序就保证了第一关键字从大到小，并且第二关键字也是从大到小...

废话不多说了，直接看代码吧...注释里面写了一些。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6+;

int n;

char s[N];

int x[N],y[N],sa[N],c[N];

void Get_sa(int m){

    n=strlen(s);

    for(int i=;i<m;i++) c[i]=;

    for(int i=;i<n;i++) c[x[i]=s[i]]++;//基数排序基本思想，c数组相当于一个桶

    for(int i=;i<m;i++) c[i]+=c[i-];

    for(int i=n-;i>=;i--) sa[--c[x[i]]]=i;//求出sa数组，这里--c[x[i]]]是用来求出sa数组的下标的，注意弄懂sa数组的含义！！

    for(int k=;k<=n;k++){

        int p=;

        for(int i=n-k;i<n;i++) y[p++]=i;

        for(int i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;//第二关键字,y[i]表示与第i小的第二关键字配对的第一关键字位置

        for(int i=;i<m;i++) c[i]=;

        for(int i=;i<n;i++) c[x[i]]++;

        for(int i=;i<m;i++) c[i]+=c[i-];

        for(int i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];//倒序很巧妙，第二关键字最大的同时，第一关键字也是尽可能大的，sa数组的求法可参见上面

        swap(x,y);

        p=;x[sa[]]=;

        for(int i=;i<n;i++)

            x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;//分别比较第一关键字和第二关键字

            //这里x[i]表示的是后缀i的大小为多少，这里相当于将第一、第二关键字合并为第一关键字

        if(p>=n) break ;

        m=p;

    }

}

int main(){

    scanf("%s",s);

    Get_sa();

    int n=strlen(s);

    for(int i=;i<n;i++) cout<<sa[i]+<<" ";

    return ;

}

巴特西

洛谷：P3809 【模板】后缀排序（后缀数组模板）

P3809 【模板】后缀排序

题目背景

题目描述

输入输出格式

输入输出样例

最新文章

热门文章