BZOJ1031

前一段时间终于看明白了后缀数组，记录一下主要的做过的题目，主要的按照黄学长的BLOG作的，主要是为了记模板。原理还是上网自己查一下吧！代码会加简单的注释。

************************************************************************************************************

1031: [JSOI2007]字符加密Cipher

Time Limit: 10 Sec Memory Limit: 162 MB

Description

　　喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法

：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作：

JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序：07JSOI 7JSOI0 I07JSO JSOI07

OI07JS SOI07J读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是

突然想出来的，那就^^）。但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

Input

　　输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母、数字，也可以是符号等。

Output

　　输出一行，为加密后的字符串。

Sample Input

JSOI07

Sample Output

I0O7SJ

HINT

对于100%的数据字符串的长度不超过100000。

***********************************************************************************************

题意：把字符环从不同的地方拆开成为n条链，再把链排序后，依次输出各个链的最后一个字符。

题解：把环从任意一个位置拆开，在接上一条，从而求后缀数组，用SA数组加上n，如果不超出范围（n---2*n-1）就可以输出。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn=200005;

 4 char c[maxn];　　　　//原字符串

 5 int s[maxn],sa[maxn],cs[maxn],rank[maxn],saf[maxn];　　
//s[]字符串的内容，记录的是数字，sa[i]排名第i的后缀的开始位置，cs[]用来统计次数，rank[i]第i个后缀的排名，saf[]辅助数组，第二关键字的排名，含义与sa相同

 6 int height[maxn];

 7 int n,m,nn;

 8 void init()　　//初始化，读入

 9 {

10     scanf("%s",c+1);

11     nn=n=strlen(c+1);

12     for(int i=1;i<n;++i)c[i+n]=c[i];

13     n=n*2-1;

14     for(int i=1;i<=n;++i)s[i]=c[i];

15 }

16 void rsort()　　//基数排序

17 {

18     for(int i=0;i<=m;++i)cs[i]=0;　　　　　　　　　　　　　　　　//所有次数清0

19     for(int i=1;i<=n;++i)cs[rank[saf[i]]]++;　　　　　　　　　　//第二关键字排名为i的串的排名（rank）的次数++，排名就是

20     for(int i=1;i<=m;++i)cs[i]+=cs[i-1];　　　　　　　　　　　　//次数累加

21     for(int i=n;i>=1;--i)sa[cs[rank[saf[i]]]--]=saf[i];　　　　//第二关键字排名i的串的排名次数--，得到它的名次，sa[名次]=第二关键字排名为i的串

22 }

23 int cmp(int *f,int x,int y,int w)

24 {

25     return f[x]==f[y] && f[x+w]==f[y+w];　　　　　　//第一第二关键字都想等

26 }

27 void suffix()

28 {

29     for(int i=1;i<=n;++i)rank[i]=s[i],saf[i]=i;　　　　//把字符直接复制给rank[]，它的大小就可以当作排名。saf[]赋值为i不印象排名

30     m=127;rsort();　　　　　　　　　　　　　　　　　　　　　　//m为宽敞关键字的最大范围

31     for(int p=1,w=1,i;p<n;w<<=1,m=p)　　　　　　　　　　　　//w为倍增的宽度，p为离散后的名次数（防止重名次）

32     {

33         for(p=0,i=n-w+1;i<=n;++i)saf[++p]=i;　　　　　　//从上一次的sa直接计算saf。第二关键字已经出了n的范围的一定排在前面，此时的p只是第二关键字的记数变量，没有起到上面的提到的作用

34         for(int i=1;i<=n;++i)if(sa[i]>w)saf[++p]=sa[i]-w;　　　　//只有sa[]>w，它才能用来作为第二关键字

35         rsort();swap(rank,saf);rank[sa[1]]=p=1;　　　　　　　　　　//用p记录离散后的名次

36         for(int i=2;i<=n;++i)rank[sa[i]]=cmp(saf,sa[i],sa[i-1],w)?p:++p;　　　　//可以重名次

37     }

38

39     int j,k=0;

40     for(int i=1;i<=n;height[rank[i++]]=k)　　　　//计算height[]

41         for(k=k?k-1:k,j=sa[rank[i]-1];s[i+k]==s[j+k];++k);

42

43 }

44 void work()

45 {

46     for(int i=1;i<=n;++i)

47     {

48         if(sa[i]<=nn)printf("%c",s[sa[i]+nn-1]);

49     }

50 }

51 int main()

52 {

53     init();

54     suffix();

55     work();

56     return 0;

57 }

巴特西