这是一道模版题。
读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 11 到 nn。
输入格式:
一行一个长度为 nn 的仅包含大小写英文字母或数字的字符串。
输出格式:
一行,共n个整数,表示答案。
输入样例#1:
ababa
输出样例#1:
5 3 1 4 2
n <= 10^6n<=106
看了一下午的后缀数组
基数排序的思想我懂啊。,
倍增的思想我懂啊。。
后缀数组的思想我也懂啊。。
为毛代码一行都看不懂啊。。。。。。。。。。。。。。。。。。。。。。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int MAXN=1000001;
8 void read(int &n)
9 {
10 char c='+';int x=0;bool flag=0;
11 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
12 while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
13 flag==1?n=-x:n=x;
14 }
15 int tax[MAXN];// 基数排序的辅助数组
16 int tp[MAXN];//基数排序的第二关键字
17 int a[MAXN];// 字符串数组
18 int sa[MAXN];//
19 int rak[MAXN];
20 int n,m;
21 void qsort()
22 {
23 for(int i=0;i<=m;i++) tax[i]=0;
24 for(int i=1;i<=n;i++) tax[rak[tp[i]]]++;
25 for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
26 for(int i=n;i>=1;i--) sa[tax[rak[tp[i]]]--]=tp[i];
27 }
28 int comp(int *f,int x,int y,int l)
29 {
30 return (f[x]==f[y]&&f[x+l]==f[y+l]);
31 }
32 void suffix_ar()
33 {
34 for(int i=1;i<=n;i++)
35 rak[i]=a[i],tp[i]=i;
36 m=127,qsort();
37 for(int w=1,p=1,i;p<n;w+=w,m=p)
38 {
39 for(p=0,i=n-w+1;i<=n;i++)
40 tp[++p]=i;
41 for(int i=1;i<=n;i++)
42 if(sa[i]>w)
43 tp[++p]=sa[i]-w;
44 qsort(),swap(rak,tp),rak[sa[1]]=p=1;
45 for(int i=2;i<=n;i++)
46 rak[sa[i]]=comp(tp,sa[i],sa[i-1],w)? p:++p;
47 }
48 for(int i=1;i<=n;i++)
49 printf("%d ",sa[i]);
50 }
51 int main()
52 {
53 string s;
54 cin>>s;
55 n=s.length();
56 for(int i=0;i<(s.length());i++)
57 a[i+1]=s[i]-48;
58 suffix_ar();
59 return 0;
60 }