3135. 数据压缩

单点时限: 2.0 sec

内存限制: 256 MB

RLE (Run Length Encoding)算法是一个简单高效的无损数据压缩算法。

算法的基本思路 :

(1)、把数据看成一个线性序列;

(2)、用一个字节表示数据重复的次数,然后在这个字节后面存储对应的数据。

例如,数据序列 AAAAABBCD,采用 RLE 算法压缩为:5A2B1C1D。

(3)、由于只采用一个字节存储数据重复次数,其最大值为 255;因此对于数据序列的某一个数据重复次数大于 255 时,则当计数到 255 时就必须强制将计数值和当前数据值写入,然后再重新开始计数。

例如,数据序列:

采用 RLE 算法压缩为:255A7A5B2C1D1E3P

输入格式

第 1 行:一个整数 $T$ ($1 \le T \le 10$) 为问题数。

接下来 T 行,每行输入一段文本数据,文本长度不超过 500 个字符。

文本由可打印字符组成。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)。然后对应每个问题 , 在一行中输出压缩后的结果。

样例

Input
3
AAAAABBCD
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBCCDEPPP
fggggdfeir9999000;;dqqqq234ererrrrrrrrrrrrvvvvvvz
Output
case #0:
5A2B1C1D
case #1:
255A7A5B2C1D1E3P
case #2:
1f4g1d1f1e1i1r49302;1d4q1213141e1r1e12r6v1z

272 人解决,326 人已尝试。

366 份提交通过,共有 893 份提交。

2.1 EMB 奖励。

创建: 4 年,9 月前.

修改: 2 年,2 月前.

最后提交: 6 天,2 小时前.

来源: N/A

题目标签