CCC '10 S2 - Huffman Encoding

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
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 0s and 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, B, C, D, E\}:

That is, A is encoded as 00, B is encoded as 01, C is encoded as 10, D is encoded as 110 and E is encoded as 111.

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.

Input Specification

The first line of input will be an integer k (1 \le k \le 20), representing the number of characters and associated codes. The next k lines each contain a single character, followed by a space, followed by the binary sequence (of length at most 10) representing the associated code of that character. You may assume that the character is an alphabet character (i.e., a \ldots z and A \ldots Z). You may assume that the sequence of binary codes has the prefix-free property. On the k + 2nd 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 k + 2nd line contains no more than 250 binary digits.

Output Specification

On one line, output the characters that correspond to the given binary sequence.

Sample Input

5
A 00
B 01
C 10
D 110
E 111
00000101111

Output for Sample Input

AABBE

Comments


  • 2
    AWB  commented on Jan. 26, 2018, 9:48 p.m.

    It says in the problem statement "The next k lines each contain a single character, followed by a space, followed by the binary sequence (of length at most 10)." This is not true of all the test cases (e.g., test case 2).


  • 0
    albertlai431  commented on Sept. 25, 2017, 5:07 p.m.

    Why am I getting the middle 2 incorrect???