#include <fstream>
#include <iostream>
#include <queue>
#include <tuple>
#include <map>
#include <string>
#include <assert.h>

using namespace std;
ifstream fin("t.in");
ofstream fout("t.out");

typedef tuple<int, char> TElem;

class Node{
public:
	Node() = default;
	Node(TElem& _e) : e{ _e }, ns{ nullptr }, nd{ nullptr } {};
	Node(TElem& _e, Node* _ns, Node* _nd ) : e{ _e }, ns{ _ns }, nd{ _nd } {};
	Node(const Node& n) = default;
	Node& operator=(Node&& n) noexcept { e = n.e; ns = n.ns; nd = n.nd; return *this; };
	TElem& e;
	Node* ns;
	Node* nd;
};

struct compare {
	bool operator()(Node* n1, Node* n2) {
		return get<0>(n1->e) > get<0>(n2->e) || (get<0>(n1->e) == get<0>(n2->e) && get<1>(n1->e) > get<1>(n2->e));
	}
};

//frequency, character, node is char of sum of frequencies( nod ajutator -> 0, else 1)
priority_queue < Node*, vector<Node*>, compare> pq;
map<char, string>m;
string s, rez, exp_rez, rez_decodare;
int fv[260];
size_t n, i, p;

void map_tree(Node* n, string& cod) {
	if (n->ns == nullptr) {
		m[get<1>(n->e)] = string{ cod };
		cod.pop_back();
		return;
	}
	cod += '0';
	map_tree(n->ns, cod);
	cod += '1';
	map_tree(n->nd, cod);
	if (!cod.empty()) {
		cod.pop_back();
	}
}

void codare_huffman() {
	size_t i;
	for (i = 1; i < n; i++) {
		auto* ns = pq.top();
		pq.pop();
		auto* nd = pq.top();
		pq.pop();
		auto* e = new TElem{ get<0>(ns->e)+get<0>(nd->e), min(get<1>(ns->e), get<1>(nd->e))};
		auto* n = new Node{ *e, ns, nd };
		pq.push(n);
	}
	string cod;
	map_tree(pq.top(), cod);
	fout << '\n';
	for (auto el : m) {
		fout << el.first << ' ' << el.second << '\n';
	}
	for (auto c : s) {
		rez+= m[c];
	}
	fout << rez <<"\n\n";
	assert(rez == exp_rez);
}

void decodare_huffman() {
	p = 0;
	while (p < exp_rez.size() - 1) {
		auto* n = pq.top();
		while (n->ns != nullptr) {
			if (exp_rez[p] == '0') {
				n = n->ns;
			}
			else {
				n = n->nd;
			}
			p++;
		}
		rez_decodare += get<1>(n->e);
	}
	fout << rez_decodare;
	assert(rez_decodare == s);
}

int main() {
	getline(fin, s);
	getline(fin, exp_rez);
	for (auto c : s) {
		fv[c] += 1;
	}
	for (i = 0; i < 255; i++) {
		if (fv[i] > 0) {
			auto* e = new TElem{ fv[i], i };
			auto* n = new Node{ *e };
			pq.push(n);
		}
	}
	// printare caractere si frecv
	n = pq.size();
	fout << n << '\n';
	for (i = 0; i < 255; i++) {
		if (fv[i] > 0) {
			fout << char(i) << ' ' << fv[i] << '\n';
		}
	}
	/*while (pq.size() > 0) {
		cout << get<1>(pq.top()->e);
		pq.pop();
	}*/
	codare_huffman();
	decodare_huffman();
}