NOIP2010初赛考题LZW编码是一种自适应词典编码.在编码的过程中,开始时只有一部基础构造元素的编码词典,如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,

Question

NOIP2010初赛考题
LZW编码是一种自适应词典编码.在编码的过程中,开始时只有一部基础构造元素的编码词典,如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中,并用于后继信息的编码.
举例说明,考虑一个待编码的信息串：“xyx yy yy xyx”.初始词典只有3个条目,第一个为x,编码为1:第二个为y,编码为2：第三个为空格,编码为3：于是串“xyx”的编码为1-2-1（其中-为编码分隔符）,加上后面的一个空格就是1-2-1-3.但由于有了一个空格,我们就知道前面的“xyx”是一个单词,而由于该单词没有在词典中,我们就可以自适应的把这个词条添加到词典里,编码为4,然后按照新的词典对后继信息进行编码,以此类推.于是,最后得到编码：1-2-1-3-2-2-3-5-3-4.
现在已知初始词典的3个条目如上述,则信息串“yyxy xx yyxy xyx xx xyx”的编码是:

Answer 1

"已知初始词典的3个条目如上述"即x为1,y为2,空格为3
“yyxy ”为 2-2-1-2-3 由于读到空格,且“yyxy”不在词典中,将“yyzy”加入词典,编号为4
“xx ” 为 1-1-3 由于读到空格,且“xx”不在词典中,故将“xx”加入词典,编号为5
"yyxy " 由于“yyxy”已加入词典,故直接调用,为4-3
“xyx ”为 1-2-1-3 由于读到空格,且“xyx”不在词典中,将“xyx”加入词典,编号为6
"xx " 由于“xx”已加入词典,故直接调用,为5-3
"xyx" 由于“xyx”已加入词典,故直接调用,为6(最后一位,没有空格）
故答案为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6