「uoj35」后缀排序
这是一道模板题。
读入一个长度为 n 的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。
除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出 n−1 个整数分别表示排序后相邻后缀的最长公共前缀的长度。
输入格式
一行一个长度为 n 的仅包含小写英文字母的字符串。
输出格式
第一行 n 个整数，第 i 个整数表示排名为 i 的后缀的第一个字符在原串中的位置。
第二行 n−1 个整数，第 i 个整数表示排名为 i 和排名为 i+1 的后缀的最长公共前缀的长度。
样例一
input
|
1 |
ababa |
output
|
1 2 |
5 3 1 4 2 1 3 0 2 |
explanation
排序后结果为：
- a
- aba
- ababa
- ba
- baba
限制与约定
1≤n≤105
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 100005 #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int n,k,p,q=1; char ch[N]; int a[N],v[N],h[N],sa[2][N],rk[2][N]; void mul(int *sa,int *rk,int *SA,int *RK) { for(int i=1;i<=n;i++)v[rk[sa[i]]]=i; for(int i=n;i;i--) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k; for(int i=n-k+1;i<=n;i++) SA[v[rk[i]]--]=i; for(int i=1;i<=n;i++) RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]); } void presa() { for(int i=1;i<=n;i++)v[a[i]]++; for(int i=1;i<=30;i++)v[i]+=v[i-1]; for(int i=1;i<=n;i++) sa[p][v[a[i]]--]=i; for(int i=1;i<=n;i++) rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]); for(k=1;k<n;k<<=1,swap(p,q)) mul(sa[p],rk[p],sa[q],rk[q]); for(int i=1,k=0;i<=n;i++) { int j=sa[p][rk[p][i]-1]; while(a[i+k]==a[j+k])k++; h[rk[p][i]]=k;if(k>0)k--; } } int main() { scanf("%s",ch+1); n=strlen(ch+1); for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1; presa(); for(int i=1;i<=n;i++)printf("%d ",sa[p][i]);puts(""); for(int i=2;i<=n;i++)printf("%d ",h[i]);puts(""); return 0; } |
计数器 9793915
OI 课件=>
OI 课件=>
求解释。。。
orz！orz！