bzoj 1031: [JSOI2007]字符加密Cipher

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define N 200005
 5 using namespace std;
 6 int a[N],v[N],sa[2][N],rk[2][N],n,k;
 7 char ch[N];
 8 void jin(int sa[N],int rk[N],int SA[N],int RK[N])
 9 {
10 for(int i=1;i<=n;i++)
11 v[rk[sa[i]]]=i;
12 for(int i=n;i;i--)
13 if(sa[i]>k)
14 SA[v[rk[sa[i]-k]]--]=sa[i]-k;
15 for(int i=n-k+1;i<=n;i++)
16 SA[v[rk[i]]--]=i;
17 for(int i=1;i<=n;i++)
18 RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);//这里要比较rk[],而不是ch[].
19 return;
20 }
21 int main()
22 {
23 scanf("%s",ch+1);
24 int p=0,q=1;
25 n=strlen(ch+1);
26 for(int i=1;i<=n;i++)
27 {
28 a[i]=int(ch[i]);
29 a[i+n]=a[i];
30 ch[i+n]=ch[i];
31 }
32 n<<=1;
33 for(int i=1;i<=n;i++)
34 v[a[i]]++;
35 for(int i=1;i<=256;i++)
36 v[i]+=v[i-1];
37 for(int i=1;i<=n;i++)
38 sa[p][v[a[i]]--]=i;
39 for(int i=1;i<=n;i++)
40 rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
41 for( k=1;k<n;k<<=1)
42 {
43 jin(sa[p],rk[p],sa[q],rk[q]);
44 swap(p,q);
45 }
46 for(int i=1;i<=n;i++)
47 if(sa[p][i]<=n/2)
48 printf("%c",ch[sa[p][i]+n/2-1]);
49 }