Canadian Computing Competition: 2010 Stage 1, Senior #2
There is an ingenious text-compression algorithm called Huffman coding, designed by David Huffman in 1952.
The basic idea is that each character is associated with a binary sequence (i.e., a sequence of
1s). These binary sequences satisfy the prefix-free property: a binary sequence for one character is never a prefix of another character's binary sequence.
It is worth noting that to construct a prefix-free binary sequence, simply put the characters as the leaves of a binary tree, and label the "left" edge as
0 and the "right" edge as
1. The path from the root to a leaf node forms the code for the character at that leaf node. For example, the following binary tree constructs a prefix-free binary sequence for the characters :
A is encoded as
B is encoded as
C is encoded as
D is encoded as
E is encoded as
The benefit of a set of codes having the prefix-free property is that any sequence of these codes can be uniquely decoded into the original characters.
Your task is to read a Huffman code (i.e., a set of characters and associated binary sequences) along with a binary sequence, and decode the binary sequence to its character representation.
The first line of input will be an integer (), representing the number of characters and associated codes. The next lines each contain a single character, followed by a space, followed by the binary sequence (of length at most ) representing the associated code of that character. You may assume that the character is an alphabet character (i.e., and ). You may assume that the sequence of binary codes has the prefix-free property. On the nd line is the binary sequence which is to be decoded. You may assume the binary sequence contains codes associated with the given characters, and that the nd line contains no more than binary digits.
On one line, output the characters that correspond to the given binary sequence.
5 A 00 B 01 C 10 D 110 E 111 00000101111
Output for Sample Input