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

1031: [JSOI2007]字符加密Cipher

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

Description

喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作：

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

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,,sizeof(sum));

        for (i=;i<=n;i++)sum[rank[(i+jp-)%n+]]++;

        for (i=;i<=m;i++)sum[i]+=sum[i-];

        for (i=n;i>=;i--)

                tsa[sum[rank[(i+jp-)%n+]]--]=i;

        memset(sum,,sizeof(sum));

        for (i=;i<=n;i++)sum[rank[sa[i]]]++;

        for (i=;i<=m;i++)sum[i]+=sum[i-];

        for (i=n;i>=;i--)

                sa[sum[rank[tsa[i]]]--]=tsa[i];

}

void Suffix_Array()

{

        int i,j,p;

        for (i=;i<=n;i++)trank[i]=str[i-] - ;

        for (i=;i<=n;i++)sum[trank[i]]++;

        for (i=;i<=m;i++)sum[i]+=sum[i-];

        for (i=n;i>=;i--)

                sa[sum[trank[i]]--]=i;

        rank[sa[]]=;

        for (i=,p=;i<=n;i++)

        {

                if (trank[sa[i]]!=trank[sa[i-]])p++;

                rank[sa[i]]=p;

        }

        for (j=;j<=n;j<<=)

        {

                Index_Sort(j);

                trank[sa[]]=;

                for (i=,p=;i<=n;i++)

                {

                        if (rank[sa[i]]!=rank[sa[i-]] || rank[(sa[i]+j-)%n+]!=rank[(sa[i-]+j-)%n+])p++;

                        trank[sa[i]]=p;

                }

                for (i=;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,);

        Suffix_Array();

        for (i=;i<=n;i++)

                printf("%c",str[(sa[i]-+n)%n]);

        return ;

}