[GZOI2011]图形格式

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 gif.in 输出文件 gif.out

题目描述
大家对GIF这种图形格式一定不陌生,现在我们用字符串压缩来解释GIF压缩图形的基本原理。
GIF压缩的基础是一个数字编码与字符串映射关系的字典。字典只包含可能出现在待压缩字符串中的字符或子串的映射关系,且数字编码长度相同。例如,假如要压缩的字符串可能包含所有26个大写字母,那么字典可初始化为(A,00),(B,01),(C,02),…,(Z,25),注意数字编码长度都是2。假如我们只是想压缩DNA序列,那么字典可初始化为(A,0),(T,1),(G,2),(C,3)。
压缩算法如下:
1.在字典中查找字串未压缩部分最长的前缀,将这个前缀替换成字典对应的数字编码。
2.如果字串尚有未完成压缩的部分,则在字典中添加一个映射关系(s,n),s是上一步骤找到的前缀加紧接其后的字符,n是字典中尚未使用的最小的编码。
我们以压缩字符串ABABBAABB为例说明,由于字串只包含A和B,字典初始只有两项(A,0)和(B,1)。


待压缩字串

最长前缀

替换成编码

新增字典条目

ABABBAABB

A

0

(AB,2)

0BABBAABB

B

1

(BA,3)

01ABBAABB

AB

2

(ABB,4)

012BAABB

BA

3

(BAA,5)

0123ABB

ABB

4

---

最终的压缩结果是01234。
还有一点要特别注意,当字典中不断添加新的映射关系,数字编码长度在某个步骤将突破初始化时的长度。由于字典所有数字编码长度要保持一致,这时要将字典中原有的数字编码前补0,之后的压缩按新的数字编码进行替换,而原有已替换的数字编码则不受影响。例如,ABABBAABBAABAABAB将压缩成01234027301,而不是0123402731。
请对输入的初始字典和压缩后的编码进行解压。
输入格式(GIF.in):
第一行的字符串是压缩后的数字编码。第二行是初始的字典,由一个正整数n开始,n(1<=n<=100)是字典初始的条目数,后面接着n个字符串,字典中的第一个字符串编码为0(如n>10则是00),第二个字符串编码为1,以此类推。
输出格式(GIF.out):
输出只有一行,是解压后的字符串。我们保证所有输入都是可以解压的。
样例


GIF.in

GIF.out

01234
2 A B

ABABBAABB

01234027301
2 A B

ABABBAABBAABAABAB

21104
3 BA A C

CAABAAA

01
2 JA VA

JAVA