Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 5650
Solved 2354

Description

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

JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序: 07JSOI 7JSOI0 I07JSO JSOI07OI07JS SOI07J 读出最后一列字符: I0O7SJ, 就是加密后的字符串 (其实这个加密手段实在很容易破解, 鉴于这是突然想出来的, 那就^^). 但是, 如果想加密的字符串实在太长, 你能写一个程序完成这个任务吗?

Input

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

Output

输出一行, 为加密后的字符串.

Sample Input

JSOI07

Sample Output

I0O7SJ

HINT

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

Source

后缀数组

话说我用的倍增把 x2 写成了++结果爆 TLE 调了很久很久才发现问题~

注意字符串的内容不一定是字母、数字, 也可以是符号等.

注意字符串的内容不一定是字母、数字, 也可以是符号等.

注意字符串的内容不一定是字母、数字, 也可以是符号等.

重要的事情说三遍!! !


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 800100;
#define For(_x,_y,_z) for(int _x=_y;_x<=_z;_x++)
#define ForR(_x,_y,_z) for(int _x=_y;_x>=_z;_x--)
#define Clear(_x) memset(_x,0,sizeof(_x))

// This suffix array is only used to be sorted.
class SuffixArray
{
public:
    int n, pwn, rank[maxn], prank[maxn];
    int stra[maxn], strb[maxn], srta[maxn], srtb[maxn];
    int posa[maxn], posb[maxn], cnt[maxn];
    void init(int _n, int* arr)
    {
        n = _n;
        pwn = 1; while (pwn < n) pwn <<= 1;
        for (int i = 1; i <= n; i++)
            rank[i] = arr[i];
        for (int i = n + 1; i <= pwn; i++)
            rank[i] = 0;
        swap(n, pwn);
        return ;
    }
    void build(void)
    {
        int c = max(n, 257);
        for (int d = 1; d <= n; d <<= 1) {
            // Initialize "string" to be compared...
            For (i, 1, n)   stra[i] = rank[i],
                            strb[i] = rank[i + d];
            // Resetting counter for bit-2 to be sorted
            Clear(cnt);
            For (i, 1, n)   cnt[strb[i]]++;
            For (i, 1, c)   cnt[i] += cnt[i - 1];
            // To sort according to second position
            For (i, 1, n)   srta[cnt[strb[i]]] = stra[i],
                            srtb[cnt[strb[i]]] = strb[i],
                            posb[cnt[strb[i]]--] = i;
            // Resetting counter for bit-1 to be sorted
            Clear(cnt);
            For (i, 1, n)   cnt[srta[i]]++;
            For (i, 1, c)   cnt[i] += cnt[i - 1];
            ForR (i, n, 1)  stra[cnt[srta[i]]] = srta[i],
                            strb[cnt[srta[i]]] = srtb[i],
                            posa[cnt[srta[i]]--] = posb[i];
            // Re-updating rank array and continue
            For (i, 1, n)   rank[posa[i]] = stra[i] == stra[i - 1] && strb[i] == strb[i - 1]
                    ? rank[posa[i - 1]] : rank[posa[i - 1]] + 1;
            continue;
        }
        swap(n, pwn);
        // Reverse rank[] to be assigned / positioned easily.
        for (int i = 1; i <= n; i++)
            prank[rank[i]] = i;
        return ;
    }
} sa;

int     n, arr[maxn];
char    str[maxn], res[maxn];

void download(void)
{
    // To retrieve the sorting procedures and send to output pipeline.
    int pos = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (sa.prank[i] > n)
            continue;
        // Assign result position's value
        res[++pos] = arr[sa.prank[i] + n - 1];
    }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%s", str);
    n = strlen(str);
    For (i, 1, n) arr[i + n] = arr[i] = (int)str[i - 1];
    // Done copying... now suffix sorting.
    sa.init(n * 2, arr);
    sa.build();
    // Downloading final results and output...
    download();
    for (int i = 1; i <= n; i++)
        printf("%c", (char)res[i]);
    return 0;
}
from pydatagen import *
s_t = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`~!@#$%^&*()-=_+[]|\\:;"\',.<>?/'
s = list()
for i in s_t:
    s.append(i)
n = randrange(10, 100000)
r_l = randlist(n, s)
r = str()
for i in r_l:
    r = r + i
printf('%s\n' % r)
fclose()