[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

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

评论

还没有任何评论,你来说两句吧



新博客地址:
darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io


常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai