【传送门：BZOJ1031】
简要题意：
给出一个长度为n的字符串环，可以旋转这个字符串环，可以得到n个字符串，如：原字符串为：JSOI07，可以得到JSOI07，SOI07J，OI07JS，I07JSO，07JSOI，7JSOI0，讲这些字符串按字典序从小到大排，输出这n个字符串排序后的首字母组成的新字符串
题解：
暴力显然会爆，所以用后缀数组来做，因为字符串环可以旋转，所以我们把原字符串接在原字符串上，比如说JSOI07，我们接了之后变成JSOI07JSOI0，为什么最后的7不见了呢，因为如果有7的话就会重复使用JSOI07这个串，然后得到一个后缀数组，将首字母输出就可以了
参考代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>using namespace std;char a[210000];int sa1[210000];int Rank[210000];int Rsort[210000];int sa2[210000];int tt[210000];int s[210000];void get_sa(int n,int m){ ???memcpy(Rank,s,sizeof(Rank)); ???memset(Rsort,0,sizeof(Rsort)); ???for(int i=1;i<=n;i++) Rsort[Rank[i]]++; ???for(int i=1;i<=m;i++) Rsort[i]+=Rsort[i-1]; ???for(int i=n;i>=1;i--) sa1[Rsort[Rank[i]]--]=i; ???int ln=1,p=0; ???while(p<n) ???{ ???????int k=0; ???????for(int i=n-ln+1;i<=n;i++) sa2[++k]=i; ???????for(int i=1;i<=n;i++) if(sa1[i]-ln>0) sa2[++k]=sa1[i]-ln; ???????memset(Rsort,0,sizeof(Rsort)); ???????for(int i=1;i<=n;i++) Rsort[Rank[i]]++; ???????for(int i=1;i<=m;i++) Rsort[i]+=Rsort[i-1]; ???????for(int i=n;i>=1;i--) sa1[Rsort[Rank[sa2[i]]]--]=sa2[i]; ???????for(int i=1;i<=n;i++) tt[i]=Rank[i]; ???????Rank[sa1[1]]=1;p=1; ???????for(int i=2;i<=n;i++) ???????{ ???????????if(tt[sa1[i]]!=tt[sa1[i-1]]||tt[sa1[i]+ln]!=tt[sa1[i-1]+ln]) p++; ???????????Rank[sa1[i]]=p; ???????} ???????ln*=2;m=p; ???}}int main(){ ???scanf("%s",a+1); ???int n=strlen(a+1); ???for(int i=n+1;i<=n+n-1;i++) a[i]=a[i-n]; ???for(int i=1;i<=n+n-1;i++) s[i]=a[i]; ???get_sa(n+n-1,200); ???for(int i=1;i<=n+n-1;i++) ???{ ???????if(sa1[i]<=n) ???????{ ???????????printf("%c",a[sa1[i]+n-1]); ???????} ???} ???printf("\n"); ???return 0;}BZOJ1031: [JSOI2007]字符加密Cipher
原文地址：http://www.cnblogs.com/Never-mind/p/7804416.html