#10986. Message Decoding 消息解码
Message Decoding 消息解码
213 Message Decoding
Description
某些消息编码方案要求消息以两个部分发送。第一部分称为头部,其中包含消息的字符。第二部分包含表示消息的模式。你必须编写一个程序来解码这些消息。
编码方案的核心是一系列0和1 的“关键”字符串,如下所示:
0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001,..., 1011, 1110, 00000,...
第一个关键字符串长度是1,接下来的3个长度是2,接下来的7个长度是3,接下来的15个长度是4,以此类推。相邻的两个关键字符串如果长度相同,第二个可以通过在第一个的基础上添加1(以二进制为基)获得。注意:序列中不存在只有1 的关键字符串。
这些关键字符串依次映射到头部中的字符。第一个关键字符串(0)映射到头部的第一个字符,第二个关键字符串(00)映射到第二个字符,第k个关键字符串映射到第k个字符。例如,假设头部是:
AB#TANCnrtXc
那么,0 映射到A,00 映射到B,01 映射到#,10 映射到T,000 映射到A,……,110 映射到X,0000 映射到c。
编码后的消息只包含0 和1,并且可能包含回车符,它们应被忽略。消息分为多个段。段的前3 位表示关键字符串长度的二进制表示。例如,如果前3 位是010,那么段的其余部分由长度为2 的关键字符串(00、01 或10)组成。以段中关键字符串长度为长度的1 的字符串终止该段。因此,长度为2 的关键字符串段以11 终止。整个编码消息以000 终止,该结尾表示段中关键字符串长度为0。消息通过将段中的关键字符串一个接一个地转换为头部字符进行解码。
Input
输入文件包含多个数据集。每个数据集包含一个头部(单独一行),以及一个(可以跨多行的)消息。头部长度只受到关键字符串最大长度的限制,为7(二进制为111)。如果头部中包含重复字符,则多个关键字符串会映射到同一个字符。编码消息只包含0 和1,并且是根据描述的方案合法编码的。消息段以三位长度序列开始,并以相应长度的1 结束。段中的关键字符串长度相同,并且它们对应于头部中的字符。消息以000 终止。
消息部分中可以出现回车符,不应视为消息的一部分。
Output
对于每个数据集,程序应在单独的行上输出解码后的消息。消息之间不应有空行。
Sample Input
TNM AEIOU
0010101100011
1010001001110110011
11000
#**\
0100000101101100011100101000
Sample Output
TAN ME
##*\
$