喜欢钻研问题的JS 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。
例如‘JSOI07’,可以读作: JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序: 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。 但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?
输入输出格式
输入格式:
输入文件包含一行,欲加密的字符串。注意字符串的内容不一定是字母、数字,也可以是符号等。
输出格式:
输出一行,为加密后的字符串。
后缀数组裸题。
把字符串接到自己后面变成长度为2*len以后, 如何后求后缀排序得到sa数组和rak数组,对len长度的rak数组直接排序。
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int tx[maxn], sa[maxn], rak[maxn];
int height[maxn];
int dp[maxn][20];
int lg[maxn];
char s[maxn];
int n, m, p, k;
struct node {
int x, y, id;
}a[maxn], b[maxn];
void rsort() {
for (int i = 1; i <= m; i++) {
tx[i] = 0;
}
for (int i = 1; i <= n; i++) {
tx[a[i].y]++;
}
for (int i = 1; i <= m; i++) {
tx[i] += tx[i - 1];
}
for (int i = 1; i <= n; i++) {
b[tx[a[i].y]--] = a[i];
}
for (int i = 1; i <= m; i++) {
tx[i] = 0;
}
for (int i = 1; i <= n; i++) {
tx[b[i].x]++;
}
for (int i = 1; i <= m; i++) {
tx[i] += tx[i - 1];
}
for (int i = n; i >= 1; i--) {
a[tx[b[i].x]--] = b[i];
}
}
void ssort() {
rsort();
p = 0;
for (int i = 1; i <= n; i++) {
if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) {
++p;
}
rak[a[i].id] = p;
}
for (int i = 1; i <= n; i++) {
a[i].x = rak[i];
a[i].id = sa[rak[i]] = i;
a[i].y = 0;
}
m = p;
}
void solve(int mx) {
m = mx;
for (int i = 1; i <= n; i++) {
a[i].x = a[i].y = s[i];
a[i].id = i;
}
ssort();
for (int j = 1; j <= n; j <<= 1) {
for (int i = 1; i + j <= n; i++) {
a[i].y = a[i + j].x;
}
ssort();
if (p == n) {
break;
}
}
}
char str[maxn];
struct query {
int x, id;
}q[maxn];
int cmp(query a, query b) {
return a.x < b.x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
scanf("%s", str + 1);
int len = strlen(str + 1);
for (int i = 1; i <= len; i++) {
s[i] = str[i];
s[i + len] = str[i];
}
n = 2 * len;
solve(127);
int ans = 0;
for (int i = 1; i <= len; i++) {
q[i].x = rak[i];
q[i].id = i;
}
sort(q + 1, q + len + 1, cmp);
for (int i = 1; i <= len; i++) {
printf("%c", s[q[i].id + len - 1]);
}
printf("\n");
return 0;
}
/* JSOI07 */