PID613 / LZW编码加强版
题目描述

LZW编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编码的词典,如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,并用与后继信息的编码。

举例说明,:考虑一个待编码的信息串:“xyx yy yy xyx”. 初始词典只有3个条目,第一个为x,编码为1;第二个为Y,编码为2;第三个为空格,编码为0;(对于空格,编码在任何情况下都是0)于是串“XYX”的编码为1-2-1(其中-为编码分隔符),加上后面的一个空格就是1-2-1-3。但由于有了一个空格,我们就知道前面的“XYX”是一个单词,而由于该单词没有在词典中,我们就可以自适应的把这个词条添加到字典里,编码为4,然后按照新的词典对后继信息进行编码,依次类推。于是,最后得到编码:1-2-1-0-2-2-0-4-0-3我们可以看到,信息被压缩了。压缩好的信息传递到接受方,接受方也只要根据基础词典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。

输入格式

第一行为n,表示下一行有n个字符。

第二行有n个字符,第i个字符的编号为i,空格的编号为0。

第三行为需要解码的编码。

输出格式

输出仅一行,表示解码后的字符串。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论