3298. 哈夫曼编码

【题目描述】

计算机网络传输中需将传送的文字转换成由二进制的字符组成的字符串。例如，假设需传送的字串为”ABACCDA”，它只有四种字符，只需两个字符的串便可分辨。假设A、B、C、D的编码分别为00、0l、10和11，则上述七个字符的字串便为”00010010101100”，总长14位，对方接收时，可按二位一分进行译码。

在传送时，希望编码总长尽可能地短。如果对每个字符设计长度不等的编码，且让字串中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。

如果设计A、B、C、D的编码分别为0,01,1和10，则上述七个字符的字串可转换成总长为9的字符。但这种编码会导致无法解码，因为任一个字符的编码都不能是另一个字符的编码的前缀。

现在给你一篇待传送的文字，请你编程为每一个字符设计编码，使得编码总长最短。

【输入格式】

输入文件有一行，全部由大写英文字母组成，字符个数不超过10000个。

【输出格式】

输出文件包含若干行，每行一个字符的编码。

输出可能有多解，任意输出一种即可，可以按照任意顺序输出字符编码，具体格式参考样例。

【样例输入】

BADCADFEED

【样例输出】

A:111
B:010
C:011
D:10
E:00
F:110