// encode string using lz78:
#include <vector>
#include <unordered_map>
#include <string>
#include <utility>
#include <iostream>
#include <type_traits>
#include <iterator>

using namespace std;

template<typename T>
class vechasher: public std::unary_function<vector<T>,std::size_t> {
public:
	std::size_t operator()(const vector<T> &v) const {
		std::size_t ret = 0;
		for(auto &x : v)
			ret += std::hash<T>()(x);
		return ret;
	}
};

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	copy(begin(v),end(v),ostream_iterator<T>(os,","));
	return os;
}

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const std::pair<T1,T2> &p) {
	os << p.first << "->" << p.second;
	return os;
}

template<typename T>
auto encode(const T &s)
		-> vector<pair<int,
			typename remove_cv<
				typename remove_reference<
					decltype(*begin(s))>::type>::type>> {

	typedef typename remove_cv<
		typename remove_reference<
			decltype(*begin(s))>::type>::type unittype;

	unordered_map<vector<unittype>,int,vechasher<unittype>> dict;
	vector<pair<int,unittype>> ret;

	int foundnum = 0,maxnum = 0;
	vector<unittype> word;
	for(auto x : s) {
		word.emplace_back(x);
		auto loc = dict.find(word);
		if (loc == dict.end()) {
			ret.emplace_back(foundnum,x);
			//dict.emplace(word,++maxnum);
			dict[word] = ++maxnum;
			foundnum = 0;
			word.resize(0);
		} else foundnum = loc->second;
	}
	if (foundnum!=0) {
		auto &x = word.back();
		word.pop_back();
		auto loc = dict.find(word);
		ret.emplace_back(loc==dict.end() ? 0 : loc->second,x);
	}

	cout << "hash table useage: " << endl;
	auto nbuck = dict.bucket_count();
	for(size_t b = 0;b<nbuck;b++) {
		cout << "bucket " << b << " (" << dict.bucket_size(b) << "): ";
		for(auto x=dict.begin(b);x!=dict.end(b);++x)
			cout << x->first << "->" << x->second;
		cout << endl;
	}
	



	return ret;
}

int main(int argc, char **argv) {
	string s;
	cin >> s;
	auto encoding = encode(s);
	for(auto &x : encoding)
		cout << "(" << x.first << ',' << x.second << ") ";
	cout << endl;
}