BZOJ1031 - [JSOI2007]字符加密Cipher

2017/01/01

新年第一题!

题目描述

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

JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0

把它们按照字符串的大小排序:

07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J

读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是 突然想出来的,那就^^)。但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?

代码

原串 * 2 来拆环,然后跑裸SA。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int MSIZ = 2E5 + 1E3;

int num[MSIZ];
int sa[MSIZ], rank[MSIZ], height[MSIZ];
int wa[MSIZ], wb[MSIZ], wv[MSIZ], wd[MSIZ];

int cmp(int *r, int a, int b, int l) {
    return r[a] == r[b] && r[a+l] == r[b+l];
}

void da(int *r, int n, int m) {
    int i, j, p, *x = wa, *y = wb, *t;
    for(i = 0; i < m; i ++) wd[i] = 0;
    for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
    for(i = 1; i < m; i ++) wd[i] += wd[i-1];
    for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
    for(j = 1, p = 1; p < n; j *= 2, m = p){
        for(p = 0, i = n-j; i < n; i ++) y[p ++] = i;
        for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j;
        for(i = 0; i < n; i ++) wv[i] = x[y[i]];
        for(i = 0; i < m; i ++) wd[i] = 0;
        for(i = 0; i < n; i ++) wd[wv[i]] ++;
        for(i = 1; i < m; i ++) wd[i] += wd[i-1];
        for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i];
        for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){
            x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++;
        }
    }
}

int main() {
    char str[MSIZ];
    cin >> str;
    int n = strlen(str), len = n;
    for(int i=0;i<n;i++) str[i+n] = str[i];
    n = strlen(str);
    for(int i=0;i<=n;i++) num[i] = int(str[i]);
    da(num, n + 1, 128);
    for(int i=1;i<=n;i++) {
        if(sa[i] < len)
            putchar(str[sa[i] + len - 1]);
    }
    cout << endl;
}