#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
 
using namespace std;
int finded = 0;
struct haffnode {
    char sym;
    int freq;
    haffnode *left, *right;
};
 
void qusort(haffnode **arr, int l, int r) {
    int key = arr[(l+r)/2]->freq;
    int i = l;
    int j = r;
    do {
        while (arr[i]->freq < key) i++;
        while (arr[j]->freq > key) j--;
        if (arr[i]->freq >= arr[j]->freq) {
            haffnode *tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++; j--;
        }
 
    } while (i < j);
 
    if (i < l) qusort(arr, i, l);
    if (j > r) qusort(arr, j, r);
}
haffnode** get_frequences(int &size) {
    //ifstream fin("hin");
    map <char, int> fq;
    char t;
 
//    while (fin >> t) 
//        fq[t]++;
    FILE *fin = fopen("hin", "r");
    while (fscanf(fin, "%c", &t) != -1) {
        if ((t != '\n')&&(t != '\0'))
         fq[t]++;
    }
    fclose(fin);
 
    int i = 0;
    haffnode **arr = new haffnode*[fq.size()];
    for (map <char, int>::iterator it = fq.begin(); it != fq.end(); it++) {
        arr[i] = new haffnode;
        arr[i]->sym   = (it)->first;
        arr[i]->freq  = (it)->second;
        arr[i]->left  = NULL;
        arr[i]->right = NULL;
        i++;
    }
    size = fq.size();
    return (arr);
}
void dgout(haffnode **arr, int size, int offset) {
    for (int i = 0 + offset; i < size; i++) 
        cout << (arr[i]->sym == '\0' ? '0' : arr[i]->sym) << ":" << arr[i]->freq << " ";
    cout << endl;
}
haffnode *embrace_node(haffnode *first, haffnode *second) {
    haffnode *one = new haffnode;
    one->freq = first->freq;
    one->left = first->left;
    one->right = first->right;
    one->sym = first->sym;
 
    haffnode *two = new haffnode;
    two->freq = second->freq;
    two->left = second->left;
    two->right = second->right;
    two->sym = second->sym;
 
    haffnode *general = new haffnode;
    general->left = one;
    general->right = two;
    general->freq = first->freq + second->freq;
    general->sym = '\0';
 
    return (general);
}
void set_interval(int cnt) {
    for (int i = 0; i < cnt; i++)
        cout << " ";
 
}
void print_tree(haffnode *first, int lvl) {
    if (!first)
        return;
    print_tree(first->right, lvl+1);
    set_interval(lvl*8);
    cout << (first->sym == '\0' ? '*' : first->sym) << ":" << first->freq << endl;
    print_tree(first->left, lvl+1);
}
void get_code(haffnode *first, char symb, vector <int> &answ) {    
    if (finded) return;
    if (first == NULL) return;
    if (first->sym == symb) {
        finded = 1;
        return;
    }
 
    answ.push_back(0);
    get_code(first->left, symb, answ);
    if (finded) return;
    answ.pop_back();
 
    answ.push_back(1);
    get_code(first->right, symb, answ);
    if (finded) return;
    answ.pop_back();
}
 
int main(void) {
    int size;
    haffnode **list = get_frequences(size);
 
    int k = 0;
    int offset = 0;
    haffnode *first;
    while (k < size - 1) {
        dgout(list, size - 1, offset);
        qusort(list, offset, size - 1);
        first = embrace_node(list[0 + offset], list[1 + offset]);
        offset++;
        list[offset] = first;
        k++;
    }
    print_tree(first, 0);
 
    char tmp;
    FILE *inp = fopen("hin", "r");
    ofstream otp("hout");
    ofstream tbl("htable");
 
    vector <int> vec;
    while (fscanf(inp, "%c", &tmp) != -1) {
        if ((tmp == '\0')||(tmp == '\n'))
            continue;
 
        vec.clear();
        get_code(first, tmp, vec);
        for (int i = 0; i < vec.size(); i++)
            otp << vec[i];
        finded = 0;
    }
    otp << endl;
 
    char c;
    for (int i = 0; i < 127; i++) {
        finded = 0;
        c = (char)i;
        vec.clear();
        get_code(first, c, vec);
        if (!vec.size())
            continue;
        tbl << "| " << c << " | ";
        for (int i = 0; i < vec.size(); i++) 
            tbl << vec[i];
        tbl << " |" << endl;
        finded = 0;
    }
 
    return 0;
}