Dehuff
Time limit1sMemory limit128 MB
Given a sample string and its full binary encoding, reconstruct the unique prefix-code table for the alphabet, or report several possible tables.
- Level
Medium7 of 10
- Topics
- Tree, DFS, String, Implementation
- Solved
- No attempts yet
Problem
A data-compression scheme builds a table of variable-length binary codes, using one or more bits to represent each letter of an alphabet. Letters that occur most frequently are usually given shorter codes than letters that occur rarely. For example, over the letters A-Z the letter E generally appears in more words than Q, so E would be expected to have a shorter code than Q.
Given a sample string that uses each letter of an alphabet at least once, together with the complete binary encoding of that sample string, you can reconstruct at least one binary code table for the alphabet. For example, take the sample string CAB, which uses each letter of the alphabet {A, B, C}. If the binary encoding of CAB is 01011, then the only possible code table is:
- C = 0
- A = 10
- B = 11
Every code is a prefix code: no code in the table is a prefix of any other code (so A = 01, B = 011 would not be allowed, because A is a prefix of B). Write a program that reconstructs the binary code table from a sample string and its binary encoding. If exactly one code table is possible, print it, sorted. If more than one code table can be produced from the given data, print MULTIPLE TABLES. The entire code space is always used: there are no unused codes.
Input
The first line contains a single integer N, the number of datasets that follow. Each dataset consists of two lines. The first line is the sample string, which contains at least one occurrence of every letter (or space) in the alphabet. The second line is the binary encoding of that sample string. Sample strings contain only upper-case letters and spaces.
Output
For each dataset, first print a line identifying it in the form DATASET #n, where n is the dataset number from 1 to N. If more than one code table can represent the alphabet, print MULTIPLE TABLES on the next line and move on to the next dataset. If exactly one code table is possible, print one line for each character of the alphabet, showing the character, a space, an equals sign (=), a space, and the binary code for that character. List the characters in ascending order of their ASCII values.