bzoj 1031: [JSOI2007]字符加密Cipher 後綴數組模板題

浏览数：59 / 时间：2015年06月09日

1031: [JSOI2007]字符加密Cipher

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3157 Solved: 1233
[Submit][Status]

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。

　　後綴數組不好理解，可以直接背下來，反正我是覺得基數排序後半部分簡直無法理解。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 110000
#define MAXV MAXN*2
#define MAXE MAXV*200
typedef long long qword;
int n,m;
char str[MAXN];
int sa[MAXN];
int tsa[MAXN];
int rank[MAXN];
int trank[MAXN];
int sum[MAXN];
void Index_Sort(int jp)
{
        int i;
        memset(sum,0,sizeof(sum));
        for (i=1;i<=n;i++)sum[rank[(i+jp-1)%n+1]]++;
        for (i=1;i<=m;i++)sum[i]+=sum[i-1];
        for (i=n;i>=1;i--)
                tsa[sum[rank[(i+jp-1)%n+1]]--]=i;
        memset(sum,0,sizeof(sum));
        for (i=1;i<=n;i++)sum[rank[sa[i]]]++;
        for (i=1;i<=m;i++)sum[i]+=sum[i-1];
        for (i=n;i>=1;i--)
                sa[sum[rank[tsa[i]]]--]=tsa[i];
}
void Suffix_Array()
{
        int i,j,p;
        for (i=1;i<=n;i++)trank[i]=str[i-1] - 32;
        for (i=1;i<=n;i++)sum[trank[i]]++;
        for (i=1;i<=m;i++)sum[i]+=sum[i-1];
        for (i=n;i>=1;i--)
                sa[sum[trank[i]]--]=i;
        rank[sa[1]]=1;
        for (i=2,p=1;i<=n;i++)
        {
                if (trank[sa[i]]!=trank[sa[i-1]])p++;
                rank[sa[i]]=p;
        }
        for (j=1;j<=n;j<<=1)
        {
                Index_Sort(j);
                trank[sa[1]]=1;
                for (i=2,p=1;i<=n;i++)
                {
                        if (rank[sa[i]]!=rank[sa[i-1]] || rank[(sa[i]+j-1)%n+1]!=rank[(sa[i-1]+j-1)%n+1])p++;
                        trank[sa[i]]=p;
                }
                for (i=1;i<=n;i++)
                        rank[i]=trank[i];
        }
}
int main()
{
        freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
        int i,j,k;
        int x,y,z;
//        for(i=1;i<100;i++)
//                printf("%d %c\n",i,i);
        scanf("%s\n",&str);
        n=strlen(str);
        m=max(n,300);
        Suffix_Array();
        for (i=1;i<=n;i++)
                printf("%c",str[(sa[i]-2+n)%n]);
        return 0;
}