#P6586. 压缩算法
压缩算法
压缩算法
题目描述
数据压缩是我们信息社会中的一项重要技术。它的目的是将给定的字符串编码为(尽可能)更紧凑的编码字符串,以便能够高效地存储和/或传输。
你需要设计一种新颖的压缩算法,以确保即使编码字符串被反转后,也能够解码为原字符串。
目前,你正在考虑以下规范作为候选方案:
- 给定的字符串是一串十进制数字,即由0至9组成的序列。
- 编码字符串由一系列编码词组成,每个编码词包含两个十进制数字A和L。因此,编码字符串是一串偶数个十进制数字。
- 编码字符串 的解码过程如下。为了简化,每个十进制数字(如 或 )也视作它所表示的 至 的整数。
解码时按顺序处理每个编码词 :
- 若 ,向已解码串末尾追加一个数字 。
- 否则,若 ,不做任何操作。
- 否则,若 大于当前已解码串的长度,报告错误。
- 否则,重复 次:读取当次追加前已解码串的倒数第 个数字,将它追加到串末尾。每次追加后,下次读取的串也随之改变。
上述分支按顺序判断;特别地,编码词 00 输出一个 0,而 的编码词直接跳过,不检查距离是否越界。反转指反转整个编码串的所有数字,因此 25 反转为 52,不只是调换编码词的先后顺序。
例如,编码字符串 000125 被解码为字符串 0101010,步骤如下:
- 第一个编码词
00输出0。 - 第二个编码词
01输出1。 - 最后一个编码词
25的第一个数字2表示需要输出当前已解码数字中倒数第二个数字,共需重复输出五次。- 第一次重复时,已解码的数字为
0和1,倒数第二个数字为0,输出0。 - 第二次重复时,已解码的数字为
0, 1, 0,倒数第二个数字为1,输出1。 - 再重复三次分别输出
0, 1, 0。
- 第一次重复时,已解码的数字为
若一串编码词没有产生错误,则该编码字符串是有效的。如果编码字符串的反转也是有效的且原字符串和其反转均解码为相同的字符串,则称该编码字符串是可逆的。
例如,编码字符串 000125 不是可逆的,因为其反转 521000 会产生错误,不是有效编码。编码字符串 0010 虽然反转后有效,但不是可逆的,因为解码得到的结果不同。相反,编码字符串 0015599100 是可逆的,因为其反转 0019955100 也是有效的,并且都解码为 00000000000000000。
你希望评估此压缩方法在各种情况下的表现。你的任务是编写一个程序,对于任意给定的数字字符串,找到能够解码为该字符串的最短可逆编码字符串。
输入格式
输入包含一行,由一个非空的十进制数字字符串 s 组成。字符串的长度不超过500。
输出格式
输出能够解码为 s 的最短可逆编码字符串。如果存在多个具有相同最短长度的解码方案,请输出按字典序最小的那个。注意,可以证明对于任意输入字符串,总能存在一个可逆的编码字符串(例如,参见样例输出4)。
样例输入 1
00000000000000000
样例输出 1
0015599100
样例输入 2
0101010
样例输出 2
000122221000
样例输入 3
123123123123123123123123123123
样例输出 3
01020336699993302010
样例输入 4
123456789
样例输出 4
010203040506070809908070605040302010
相关
在以下作业中: