1631: 哈夫曼编码的解码
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：18
解决：16
题目描述
Huffman编码是一种变长的编码方案，数据的编码因其使用频率不同而长短不一。使用频率高的编码较短，使用频率低的编码较长，从而保证所有数据的编码总长最短。
请你采用Huffman编码对给定的字符串进行数据压缩。
设有“AAAABBBCDDBBAAA”字符串，根据Huffman编码方式进行编码，每个字符的编码是：
A:0
B:11
C:100
D:101
则上述字符串“AAAABBBCDDBBAAA”编码后变成：00001111111001011011111000
请你编程将给定的字符串编码成哈夫曼编码并输出。
输入
输入有多组。
每组一行，是个由大写字母构成的字符串。
输出
输出该字符串的哈夫曼编码
样例输入 复制
AAAABBBCDDBBAAA样例输出 复制
00001111111001011011111000提示
先统计每个字符出现的频率，依据这个频率构造哈夫曼树，然后对字母进行编码，最后输出。