[BZOJ 1031][JSOI 2007] 字符加密Cipher【后缀数组】

• 2018-02-23
• 0
• 0

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

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;
}