首页 > 代码库 > 1500 后缀排序
1500 后缀排序
1500 后缀排序
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
天凯是MIT的新生。Prof. HandsomeG给了他一个长度为n的由小写字母构成的字符串，要求他把该字符串的n个后缀(suffix)从小到大排序。
何谓后缀？假设字符串是S=S1S2……Sn，定义Ti=SiSi+1……Sn。T1, T2, …, Tn就叫做S的n个后缀。
关于字符串大小的比较定义如下（比较规则和PASCAL中的定义完全相同，熟悉PASCAL的同学可以跳过此段）：
若A是B的前缀，则A<B；否则令p满足：A1A2…Ap-1=B1B2…Bp-1，Ap<>Bp。如果Ap<Bp，则A<B；否则A>B。
输入描述 Input Description
第一行一个整数n(n<=15000)
第二行是一个长度为n字串。
输出描述 Output Description
输出文件包含n行，第i行是一个整数pi。表示所有的后缀从小到大排序后是Tp1, Tp2, …, Tpn。
样例输入 Sample Input
4
abab
样例输出 Sample Output
3
1
4
2
数据范围及提示 Data Size & Hint
说明：后缀排序后的顺序是T3=”ab”, T1=”abab”, T4=”b”, T2=”bab”。所以输出是3, 1, 4, 2。
分类标签 Tags 点此展开
后缀树组 树结构
//后缀数组模板题目 #include<cstdio>#include<cstring>using namespace std;const int N=1e5+7;int len,maxx,sa[N],tsa[N],rank[N],trank[N],c[N];char s[N];void DA(){ int p; memset(c,0,sizeof c);maxx=256; for(int i=1;i<=len;i++) c[rank[i]=s[i]]++; for(int i=2;i<=maxx;i++) c[i]+=c[i-1]; for(int i=len;i;i--) sa[c[rank[i]]--]=i; trank[sa[1]]=p=1; for(int i=2;i<=len;i++){ if(rank[sa[i]]!=rank[sa[i-1]]) p++; trank[sa[i]]=p; } for(int i=1;i<=len;i++) rank[i]=trank[i]; for(int k=1;p<len;k<<=1,maxx=p){ p=0; for(int i=len-k+1;i<=len;i++) tsa[++p]=i; for(int i=1;i<=len;i++) if(sa[i]>k) tsa[++p]=sa[i]-k; memset(c,0,sizeof c); for(int i=1;i<=len;i++) trank[i]=rank[tsa[i]]; for(int i=1;i<=len;i++) c[trank[i]]++; for(int i=2;i<=maxx;i++) c[i]+=c[i-1]; for(int i=len;i;i--) sa[c[trank[i]]--]=tsa[i]; trank[sa[1]]=p=1; for(int i=2;i<=len;i++){ if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++; trank[sa[i]]=p; } for(int i=1;i<=len;i++) rank[i]=trank[i]; }}int main(){ scanf("%d%s",&len,s+1); DA(); for(int i=1;i<=len;i++) printf("%d\n",sa[i]); return 0;}
1500 后缀排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。