#include<iostream>
#include<string>
#include<list>
#include<algorithm>
#include<fstream>
using namespace std;class node
{public:node *left;node *right;string code;		//编码char data;int value;			//权值node(){left=NULL;right=NULL;value=0;}
};
struct cmp						//函数对象 ,用于list的sort函数
{bool operator()(const node * x, const node* y ){return x-> value < y-> value;}
};int getnode(char data,int value,list<node*> &res)
{node *temp=new node;						//每个数据生成一个结点temp->data=data;temp->value=value;res.push_back(temp);return 0;
}int getnewnode(list<node*> &res)		//取两个权值最小的结点生成新的结点
{node *left=new node;				//最小的取为左子树left=res.front();res.pop_front() ;node *right=new node;				//第二小的取为右子树right=res.front();res.pop_front() ;node *cur=new node;		//创建新节点，连接左右子树cur->value=left->value+right->value;cur->left=left;cur->right=right;res.push_back(cur);return 0;
}void nodecode(node* cur,list<node*> &cod)	//为每个叶子结点进行编码
{if(cur->left!=NULL){cur->left->code="0"+cur->code;nodecode(cur->left,cod);}if(cur->right!=NULL){cur->right->code="1"+cur->code;nodecode(cur->right,cod);}if(cur->left==NULL&&cur->right==NULL){reverse(cur->code.begin(),cur->code.end());cod.push_back(cur);							//每个叶子结点加到list中cout<<cur->data<<":"<<cur->code<<endl;}
}void Hofmanntreecode (node* cur,list<node*> &res) //霍夫曼树编码
{cur->left->code="0";cur->right->code="1";nodecode(cur->left,res);nodecode(cur->right,res);
}string Hofmannencode(int fre[128],string a ,list<node*> &res)		//霍夫曼编码，参数：26个字母出现次数，目标字符串，霍夫曼树结点list
{int count=0;				//有效字符数 for(int i=0; i<128; i++)		//字符生成结点{if(fre[i]!=0){getnode(char(i),fre[i],res);count++;}}for(int i=0; i<count-1; i++)		//选取权值最小的两个生成新结点{res.sort(cmp());getnewnode(res);}node *cur=new node;				//为每个叶子结点编码cur=res.front();res.clear();Hofmanntreecode(cur,res);string code[128];for(list<node*>::iterator it=res.begin(); it!=res.end(); it++)	//得到每个字符的编码 {code[(**it).data]=(**it).code;}string result;for(int i=0; i<a.length(); i++)			//进行编码 {result+=code[a[i]];}return result;}string getstring(string yourstring, int pos1,  int pos2 )	//字符串切片，得到字符串从pos1到pos2位置的字符串，不包括pos2
{string result;for(int i=pos1; i<pos2; i++){result+=yourstring[i];}return result;
}string Hofmanndecode(string result,string code[128])	//霍夫曼解码，参数：26个字母编码
{string decode;int pos=0;int max=1;for(int i=0; i<128; i++){if(max<code[i].length())max=code[i].length();}while(pos<result.length()){for(int i=0; i<128; i++)				//每几个编码与字母的编码匹配{for(int x=1; x<=max; x++)			//有x个编码一起匹配，知道超出字母最长的编码或者匹配到{if(getstring(result,pos,pos+x)==code[i]){pos+=x;					//移动x个位置decode+=char(i);					//进行解码 break;}}}}return decode;}int main(void)
{list<node*> res;string yourstr;getline(cin,yourstr);int fre[128];for(int i=0; i<128; i++)				//初始化{fre[i]=0;}for(int i=0; i<yourstr.length(); i++)		//统计每个字母出现的次数{fre[yourstr[i]]++;}string result;result=Hofmannencode(fre,yourstr,res);			//霍夫曼编码，参数：26个字母出现次数，目标字符串，霍夫曼树结点liststring code[128];while(!res.empty()){code[res.front()->data]=res.front()->code;res.pop_front();}string decode;decode=Hofmanndecode(result,code);			//霍夫曼解码，参数：26个字母编码cout<<" text :"<<yourstr<<endl;cout<<"encode:"<<result<<endl;cout<<"decode:"<<decode;
}