题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1031
思路：加倍成环，然后跑一次后缀数组就好了。****
******第一次写后缀数组，写得很渣。。代码长，速度又慢。。。******
代码1:****（基数排序写得好长555 速度还渣得可怜： ）：
dcc451da81cb39dbc818087cd2160924ab18303b.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXN 200001
#define Bit(x)(int(log(x)/log(10))+1)
#define Digit(x,y)((x/EXP[y-1])%10)
struct saver {
int x,y,t;
} b[MAXN];
char s[MAXN],c[MAXN];
int n,m;
int sa[MAXN],rank[MAXN];
int EXP[10];
saver w[2][10][MAXN];
int num[2][10];
void Sort() {
int d1=0,d2=0,k=0;
memset(num,0,sizeof(num));
num[k][0]=m;
for (int i=0;i++<m;) w[k][0][i]=b[i],d1=max(d1,Bit(b[i].x)),d2=max(d2,Bit(b[i].y));
for (int i=0;i++<d2;) {
for (int j=0;j<10;j++) num[k^1][j]=0;
for (int j=0;j<10;j++) {
for (int h=0;h++<num[k][j];) {
w[k^1][Digit(w[k][j][h].y,i)][++num[k^1][Digit(w[k][j][h].y,i)]]=w[k][j][h];
}
}
k^=1;
}
for (int i=0;i++<d1;) {
for (int j=0;j<10;j++) num[k^1][j]=0;
for (int j=0;j<10;j++) {
for (int h=0;h++<num[k][j];) {
w[k^1][Digit(w[k][j][h].x,i)][++num[k^1][Digit(w[k][j][h].x,i)]]=w[k][j][h];
}
}
k^=1;
}
int h=0;
for (int i=0;i<10;i++) {
for (int j=0;j++<num[k][i];) {
b[++h]=w[k][i][j];
}
}
}
bool cmp(saver x,saver y) {
return (x.x!=y.x)||(x.y!=y.y);
}
void Make() {
b[0].x=b[0].y=0;
for (int i=0;i++<m;) rank[i]=int(s[i]);
int j=1,R;
do {
for (int i=0;i++<m;) {
b[i].x=rank[i];
b[i].y=(i+j<=m)?rank[i+j]:0;
b[i].t=i;
}
j<<=1;
Sort();
R=0;
for (int i=0;i++<m;) {
if (cmp(b[i],b[i-1])) R++;
rank[b[i].t]=R;
}
} while (R<m&&j<=m);
for (int i=0;i++<m;) sa[rank[i]]=i;
}
int main() {
EXP[0]=1;
for (int i=1;i<10;i++) EXP[i]=EXP[i-1]*10;
scanf("%s",&c);
n=strlen(c);
for (int i=0;i<n;i++) s[i+1]=s[i+n+1]=c[i];
m=n*2;
Make();
for (int i=0;i++<m;) {
if (sa[i]<=n) printf("%c",s[sa[i]+n-1]);
}
printf("\n");
return 0;
}
代码2:(<algorithm>的sort()代替基数排序):
3812b31bb051f81928b56d60d8b44aed2e73e70c.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXN 200001
#define Bit(x)(int(log(x)/log(10))+1)
#define Digit(x,y)((x/EXP[y-1])%10)
struct saver {
int x,y,t;
} b[MAXN];
char s[MAXN],c[MAXN];
int n,m;
int sa[MAXN],rank[MAXN];
int EXP[10];
saver w[2][10][MAXN];
int num[2][10];
bool Cmp(saver x,saver y) {
return (x.x<y.x)||(x.x==y.x&&x.y<y.y);
}
bool cmp(saver x,saver y) {
return (x.x!=y.x)||(x.y!=y.y);
}
void Make() {
b[0].x=b[0].y=0;
for (int i=0;i++<m;) rank[i]=int(s[i]);
int j=1,R;
do {
for (int i=0;i++<m;) {
b[i].x=rank[i];
b[i].y=(i+j<=m)?rank[i+j]:0;
b[i].t=i;
}
j<<=1;
sort(b+1,b+m+1,Cmp);
R=0;
for (int i=0;i++<m;) {
if (cmp(b[i],b[i-1])) R++;
rank[b[i].t]=R;
}
} while (R<m&&j<=m);
for (int i=0;i++<m;) sa[rank[i]]=i;
}
int main() {
EXP[0]=1;
for (int i=1;i<10;i++) EXP[i]=EXP[i-1]*10;
scanf("%s",&c);
n=strlen(c);
for (int i=0;i<n;i++) s[i+1]=s[i+n+1]=c[i];
m=n*2;
Make();
for (int i=0;i++<m;) {
if (sa[i]<=n) printf("%c",s[sa[i]+n-1]);
}
printf("\n");
return 0;
}
基数排序：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXN 200001
#define Bit(x)(int(log(x)/log(10))+1)
#define Digit(x,y)((x/EXP[y-1])%10)
char s[MAXN],c[MAXN];
int n,m;
int sa[MAXN],rank[MAXN],x[MAXN],y[MAXN],b=1,w[MAXN],r[MAXN],e[MAXN];
void Sa() {
int M=m,N;
bool flag;
for (int i=0;i++<m;) M=max(M,rank[i]=int(s[i]));
x[sa[0]=0]=y[0]=-1;
do {
for (int i=0;i++<m;) x[i]=rank[i],y[i]=i+b<=m?rank[i+b]:0;
b<<=1;
memset(w,0,sizeof(w));
for (int i=0;i++<m;) w[y[i]]++;
for (int i=0;i++<M;) w[i]+=w[i-1];
for (int i=0;i++<m;) r[w[y[i]]--]=i;
memset(w,0,sizeof(w));
for (int i=0;i++<m;) w[x[r[i]]]++;
for (int i=0;i++<M;) w[i]+=w[i-1];
for (int i=m;i;i--) sa[w[x[r[i]]]--]=r[i];
N=0;
for (int i=0;i++<m;) {
if (!(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]])) N++;
rank[sa[i]]=N;
}
} while (N<m);
}
int main() {
scanf("%s",&c);
n=strlen(c);
for (int i=0;i<n;i++) s[i+1]=s[i+n+1]=c[i];
m=n*2;
Sa();
for (int i=0;i++<m;) {
if (sa[i]<=n) printf("%c",s[sa[i]+n-1]);
}
printf("\n");
return 0;
}
