/ OPS / 题库 /

文件压缩

文件压缩

#描述#
提高文件的压缩率一直是人们追求的目标。近几年有人提出了这样一种算法,它虽然只是单纯地对文件进行重排,本身并不压缩文件,但是经这种算法调整后的文件在大多数情况下都能获得比原来更大的压缩率。<BR>
该算法具体如下:对一个长度为 n 的字符串 S ,首先根据它构造 n 个字符串,其中第 i 个字符串由将 S 的前 i - 1 个字符置于末尾得到。然后把这 n 个字符串按照首字符从小到大排序,如果两个字符串的首字符相等,则按照它们在 S 中的位置从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串 S’ ,它的长度也是 n ,并且包含了 S 中的每一个字符。最后输出 S’ 以及 S 的首字符在 S’ 中的位置 p 。举例:<BR>
S: example <BR>
1、构造n个字符串<BR>
example<BR>
xamplee<BR>
ampleex<BR>
mpleexa<BR>
pleexam<BR>
leexamp<BR>
eexampl<BR>
2、将字符串排序<BR>
ampleex<BR>
example<BR>
eexampl<BR>
leexamp<BR>
mpleexa<BR>
pleexam<BR>
xamplee<BR>
3、压缩结果<BR>
S': xelpame <BR>
p: 7 <BR>
由于英语单词构造的特殊性,某些字母对出现的频率很高,因此在 S’ 中相同的字母有很大几率排在一起,从而提高 S’ 的压缩率。虽然这种算法利用了英语单词的特性,然而在实践的过程中,人们发现它几乎适用于所有的文件压缩。<BR>
请你写一个程序,读入S’和p,输出字符串S。<BR>

#格式#
##输入格式##
有多组测试数据,执行到文件结束为止。
每组数据有三行,第 1 行是一个整数 n(1 &lt= n &lt= 10000),代表 S’ 的长度,第 2 行是字符串 S’(由小写英文字母构成),第 3 行是整数 p 。

##输出格式##
对于每组数据,输出答案 S 。每组数据占一行。

#样例1#
##样例输入1##

7
xelpame
7

##样例输出1##

example

#限制#
1000ms
32768KB

#提示#

#来源#

信息

ID
1610
难度
5
分类
category1 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者