首页 > 代码库 > bzoj 1031 [JSOI2007]字符加密Cipher
bzoj 1031 [JSOI2007]字符加密Cipher
求出来后缀数组的rank就行了,不会可以去看集训队论文。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 char c[200005]; 8 int rank[200005],sa[200005]; 9 int n; 10 int a[200005],b[200005],wb[200005],wv[200005],gs[200005]; 11 bool cmp(int *x,int a,int b,int l) 12 { 13 return x[a]==x[b]&&x[a+l]==x[b+l]; 14 } 15 void da(int *x,int *sa,int n,int m) 16 { 17 int i,j,p,*y=wb; 18 for(i=0;i<m;i++)gs[i]=0; 19 for(i=0;i<n;i++)gs[x[i]]++; 20 for(i=1;i<m;i++)gs[i]+=gs[i-1]; 21 for(i=n-1;~i;i--)sa[--gs[x[i]]]=i; 22 for(j=1,p=1;p<n;j<<=1,m=p) 23 { 24 for(i=n-j,p=0;i<n;i++)y[p++]=i; 25 for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j; 26 for(i=0;i<n;i++)wv[i]=x[y[i]]; 27 for(i=0;i<m;i++)gs[i]=0; 28 for(i=0;i<n;i++)gs[wv[i]]++; 29 for(i=1;i<m;i++)gs[i]+=gs[i-1]; 30 for(i=n-1;~i;i--)sa[--gs[wv[i]]]=y[i]; 31 swap(x,y);x[sa[0]]=0;p=1; 32 for(i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 33 } 34 } 35 int main() 36 { 37 scanf("%s",c); 38 n=strlen(c); 39 for(int i=n;i<2*n;i++)c[i]=c[i-n]; 40 for(int i=0;i<n<<1;i++)rank[i]=c[i]; 41 da(rank,sa,n*2+1,256); 42 for(int i=1;i<=n*2;i++) 43 { 44 if(sa[i]+n-1<n*2-1)putchar(c[sa[i]+n-1]); 45 } 46 return 0; 47 }
bzoj 1031 [JSOI2007]字符加密Cipher
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。