bzoj1031: [JSOI2007]字符加密Cipher 后缀数组
因为是环,搞成再在后面复制一遍即可。
#include<bits/stdc++.h> using namespace std; int n,sa[202000],rank[202000],temp[202000],p[202000],cnt[202000],height[202000],str[202000]; char s[202000]; bool epu(int x,int y,int l){return rank[x]==rank[y]&&rank[x+l]==rank[y+l];} void doubling() { str[n]=rank[n]=-1; for(int i=0;i<n;i++)str[i]=s[i]; for(int i=0;i<n;i++)sa[i]=i,rank[i]=str[i]; for(int l=0,pos=0,sig=255,i;pos<n-1;sig=pos) { for(i=n-l,pos=0;i<n;i++)p[pos++]=i; for(i=0;i<n;i++)if(sa[i]>=l)p[pos++]=sa[i]-l; memset(cnt,0,sizeof(cnt)); for(i=0;i<n;i++)cnt[rank[p[i]]]++; for(i=1;i<=sig;i++)cnt[i]+=cnt[i-1]; for(i=n-1;i>=0;i--)sa[--cnt[rank[p[i]]]]=p[i]; for(temp[sa[0]]=pos=0,i=1;i<n;i++) { if(!epu(sa[i],sa[i-1],l))pos++; temp[sa[i]]=pos; } for(i=0;i<n;i++)rank[i]=temp[i]; if(!l)l=1;else l<<=1; } } void pre() { int i,j,k; for(i=0,k=0;i<n;i++) { if(k)k--; if(rank[i]==0)continue; for(j=sa[rank[i]-1];str[j+k]==str[i+k];) k++; height[rank[i]]=k; } } int main() { //freopen("xf.in","r",stdin); scanf("%s",s); n=strlen(s); for(int i=0;i<n;i++)s[n+i]=s[i]; n*=2; doubling(); pre(); for(int i=0;i<n;i++) if(sa[i]<n/2) printf("%c",s[sa[i]+n/2-1]); printf("\n"); return 0; }
相关推荐
明学的白板 2017-12-16
辛苦的字幕君小样 2012-08-30
Huangguohao 2019-06-13
Designstuff 2018-05-17
ScalersTalk成长会 2018-01-24