Description
The data structures TAs want to pass secret messages to each other.
You will be given a text and a word. You should build a character distribution using the character frequencies of the text and do a stable sort on this list. You should then Build a Huffman tree.
Finally, encode the word based on the Huffman tree.
A Huffman tree contains characters as its leaves, and the inner nodes are the sums of the frequencies of the leaves. The edge from a parent to a left child is labeled 0, and the edge from parent to right child is labeled 1. The Huffman code for a letter will be given by the path from root to the leaf node containing that character.
In order to build a Huffman Tree:
Take 2 nodes with smallest frequency. Create a node with the sum of their frequency.
If 2 nodes have the same frequency, choose the first inputted
If an internal node and a character node have the same frequency, choose the character node
Add the nodes as the children of the new node(smallest frequency as the left child).
Add internal node to list of internal nodes & sort
Remove children from character distribution
Repeat until you only have 1 node in the character distribution (the root)
Input
-
The first line of input contains a single positive integer n (number of lines of the text) and a word, separated by a comma, followed by newline
-
The next n lines contains zero or more characters(with whitespace), they all end in newlines. This will be the text.
Output
A line of integer, without space