#include <bits/stdc++.h>

using namespace std;

int fr[128];

struct node {
    node *st, *dr;
    char ch;
    int freq;

    node(char CH, int FREQ) {
        st=dr=NULL;
        ch = CH;
        freq = FREQ;
    }
};

struct Compare {
    bool operator()(const node* lhs, const node* rhs) const {
        return lhs->freq > rhs->freq;
    }
};

string codes[128];

void find_codes(node *root, string code) {
    if(root->ch != 0)
        codes[root->ch] = code;

    if(root->st != NULL)
        find_codes(root->st, code+"0");

    if(root->dr != NULL)
        find_codes(root->dr, code+"1");
}

void encode(string text) {
    memset(fr, 0, sizeof(fr));

    for(auto it:text) ++fr[it];

    priority_queue<node*, vector<node*>, Compare > pq;
    for(int i=1;i<128;++i)
        if(fr[i])
            pq.push(new node((char)i, fr[i]));

    while(pq.size() > 1) {
        node* x = pq.top();
        pq.pop();
        node* y = pq.top();
        pq.pop();

        int freq = x->freq + y->freq;
        node *newNode = new node(0, freq);

        newNode->st = x;
        newNode->dr = y;

        pq.push(newNode);
    }

    find_codes(pq.top(), "");
}

int main()
{
    string text = "text de text";
    encode(text);

    for(auto it:text) cout << it << ' ' << codes[it] << '\n';

    return 0;
}