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+6;
- 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=0;i<m;i++) c[i]=0;
- for(int i=0;i<n;i++) c[x[i]=s[i]]++;// 基数排序基本思想, c 数组相当于一个桶
- for(int i=1;i<m;i++) c[i]+=c[i-1];
- for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;// 求出 sa 数组, 这里 --c[x[i]]] 是用来求出 sa 数组的下标的, 注意弄懂 sa 数组的含义!!
- for(int k=1;k<=n;k++){
- int p=0;
- for(int i=n-k;i<n;i++) y[p++]=i;
- for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;// 第二关键字, y[i] 表示与第 i 小的第二关键字配对的第一关键字位置
- for(int i=0;i<m;i++) c[i]=0;
- for(int i=0;i<n;i++) c[x[i]]++;
- for(int i=1;i<m;i++) c[i]+=c[i-1];
- for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];// 倒序很巧妙, 第二关键字最大的同时, 第一关键字也是尽可能大的, sa 数组的求法可参见上面
- swap(x,y);
- p=1;x[sa[0]]=0;
- for(int i=1;i<n;i++)
- x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;// 分别比较第一关键字和第二关键字
- // 这里 x[i] 表示的是后缀 i 的大小为多少, 这里相当于将第一, 第二关键字合并为第一关键字
- if(p>=n) break ;
- m=p;
- }
- }
- int main(){
- scanf("%s",s);
- Get_sa(123);
- int n=strlen(s);
- for(int i=0;i<n;i++) cout<<sa[i]+1<<" ";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2977137.html