BZOJ 1031: [JSOI2007]字符加密Cipher
1031: [JSOI2007]字符加密Cipher
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 8224 Solved: 3629
[Submit][Status][Discuss]
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 <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int sa[maxn], rk[maxn], c[maxn], y[maxn], k, p, ln;
int n, m, wr[maxn]; char ch[maxn];
void SA(int x) {
m = x;
for (int i = 1; i <= n; ++i) rk[i] = ch[i];
for (int i = 1; i <= n; ++i) c[rk[i]]++;
for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[rk[i]]--] = i;
p = 0, ln = 1;
while(p < n) {
k = 0;
for (int i = n - ln + 1; i <= n; ++i) y[++k] = i;
for (int i = 1; i <= n; ++i) if(sa[i] > ln) y[++k] = sa[i] - ln;
memset(c, 0, sizeof c);
for (int i = 1; i <= n; ++i) wr[i] = rk[i];
for (int i = 1; i <= n; ++i) c[wr[y[i]]]++;
for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i >= 1; --i) sa[c[wr[y[i]]]--] = y[i];
for (int i = 1; i <= n; ++i) wr[i] = rk[i];
rk[sa[1]] = 1; p = 1;
for (int i = 2; i <= n; ++i) {
if(!(wr[sa[i]] == wr[sa[i - 1]] && wr[sa[i] + ln] == wr[sa[i - 1] + ln])) ++p;
rk[sa[i]] = p;
} m = p; ln <<= 1;
}
}
int main() {
scanf("%s", ch + 1); n = strlen(ch + 1); int h = n;
for (int i = 1; i <= h; ++i) ch[++n] = ch[i];
SA(256);
for (int i = 1; i <= n; ++i) {
if(sa[i] <= h) printf("%c", ch[sa[i] + h - 1]);
}
return 0;
}
版权声明：本文为oi-forever原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。