[BZOJ 1031][JSOI 2007] 字符加密Cipher【后缀数组】
Problem:
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。
Source
Solution:
本题是给环的循环表示排字典序,考虑拆环成链,进行后缀排序。
后缀排序采用倍增法构造后缀数组 SA[]。然后将所有 0 < SA[i] ≤ 环长 的后缀的前一字符输出即可。
注意数组要开 2 倍。
Code: O(nlogn), n为环长度 [4616K, 712MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; char s[200005]; int n, SA[200005]; inline void buildSA(int m){ int *x = new int[200005], *y = new int[200005], *cnt = new int[200005]; for(register int i = 0; i < m; i++) cnt[i] = 0; for(register int i = 0; i < n; i++) cnt[x[i] = s[i]]++; for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[i]]] = i; for(register int k = 1; k <= n; k <<= 1){ int p = 0; for(register int i = n - k; i < n; i++) y[p++] = i; for(register int i = 0; i < n; i++) if(SA[i] >= k) y[p++] = SA[i] - k; for(register int i = 0; i < m; i++) cnt[i] = 0; for(register int i = 0; i < n; i++) cnt[x[y[i]]]++; for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i]; swap(x, y), p = 1, x[SA[0]] = 0; for(register int i = 1; i < n; i++) x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? p - 1 : p++; if(p == n) break; m = p; } } int main(){ fgets(s, 100005, stdin), n = strlen(s), s[n - 1] == '\n' ? n-- : 0; // fgets() 会将 '\n' 读入, 需要删去 for(register int i = 0; i < n; i++) s[i + n] = s[i]; // 拆环成链 n <<= 1, s[n++] = 0, buildSA(128); for(register int i = 1; i < n; i++) if(SA[i] && SA[i] <= n - 1 >> 1) putchar(s[SA[i] - 1]); return 0; }
发表评论