BZOJ 1031 [JSOI2007]字符加密Cipher 后缀数组

题意:链接方法:后缀数组解析:对于本题来说，，我们只需要将与原串一模一样的串接到原串的后面，然后再求一下SA，之后输出合法的前n个即可。代码:;char s[N<<1];int sumfix[310];int rnk[N<<1];int sa[N<<1];int use[N<<1];int que[N<<1];int n;int cmp(int *z,int a,int b,int l){return z[a]==z[b]&&z[a+l]==z[b+l];}void get_sa(int lim){int *x=use,*y=que,*t;for(int i=0;i<lim;i++)sumfix[i]=0;for(int i=0;i<n;i++)x[i]=s[i];for(int i=0;i<n;i++)sumfix[x[i]]++;for(int i=1;i<lim;i++)sumfix[i]+=sumfix[i-1];for(int i=n-1;i>=0;i–)sa[–sumfix[x[i]]]=i;int nowlen=1,head=0;for(nowlen=1,head=1;head<n;nowlen<<=1,lim=head){head=0;for(int i=n-nowlen;i<n;i++)y[head++]=i;for(int i=0;i<n;i++)if(sa[i]>=nowlen)y[head++]=sa[i]-nowlen;for(int i=0;i<lim;i++)sumfix[i]=0;for(int i=0;i<n;i++)sumfix[x[y[i]]]++;for(int i=1;i<lim;i++)sumfix[i]+=sumfix[i-1];for(int i=n-1;i>=0;i–)sa[–sumfix[x[y[i]]]]=y[i];int i;for(t=x,x=y,y=t,head=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],nowlen)?head-1:head++;}} int main(){scanf(“%s”,s);n=strlen(s);for(int i=n;i<n*2;i++)s[i]=s[i-n];n=2*n+1;//s[n-1]=0;get_sa(300);for(int i=0;i<n;i++)if(sa[i]<(n>>1))printf(“%c”,s[sa[i]+(n>>1)-1]);}

只有坚韧不拔向着目标奋进，成功后将在不远处等待着你的到来。