Сжатие сообщений

На планете, где живет инопланетянин Лучик, вся информация передается в шестнадцатеричном виде. Любое битовое сообщение разбивается на блоки по 4 бита и преобразуется в символы от 0 до F (шестнадцатеричные цифры - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). Так как каналы связи очень нагружены, в системах связи используют сжатие данных.
В большинстве систем связи на планете при передаче текстовой информации используется следующий алгоритм сжатия. Исходный текст состоит из заглавных латинских букв от A до Z и пробелов. В процессе работы алгоритма используется упорядоченный словарь. Изначально он заполняется всеми возможными односимвольными последовательностями (буквы от A до Z и пробел). В процессе работы алгоритм посимвольно просматривает исходный текст и обрабатывает его следующим образом.

Записать в текущую фразу T первый символ.
Если исходные данные окончились, вывести код T.
Считать следующий символ Q.
Если фраза TQ есть в словаре, то T = TQ, перейти на шаг 2.
Если фразы TQ нет в словаре, то вывести код T, добавить TQ в словарь, присвоить T = Q и перейти на шаг 2.
Заметим что для разархивации (декодирования) получившийся словарь не нужен. Он легко формируется в процессе разархивации.
Кодом фразы считается порядковый номер этой фразы в словаре. Для удобства перевода в шестнадцатеричный вид коды предварительно записываются в двоичном виде с переменным числом бит. Рассмотрим это на примере.
Пусть исходное сообщение имеет вид
A BIG BLACK BUG BIT A BIG BLACK DOG
В нашем алфавите 27 букв (буквы от A до Z и пробел), поэтому для его кодирования достаточно 5 бит. Начальный словарь имеет вид
A = 00000
B = 00001
....
Z = 11001
(пробел) = 11010
Процесс архивации (кодирования) представлен в таблице ниже (символ “_“ обозначает пробел).

Тек. фраза	Код на выходе	Новая запись словаря	Комментарий
A	0 = 00000
_	26 = 11010	27: A_
B	1 = 00001	28: _B
I	8 = 01000	29: BI
G	6 = 00110	30: IG
_B	28 = 11100	31: G_	далее используем 6-битные группы
L	11 = 001011	32: _BL
A	0 = 000000	33: LA
C	2 = 000010	34: AC
K	10 = 001010	35: CK
_B	28 = 011100	36: K_
U	20 = 010100	37: _BU
G_	31 = 011111	38: UG
BI	29 = 011101	39: G_B
T	19 = 010011	40: BIT
_	26 = 011010	41: T_
A_	27 = 011011	42: _A
BI	29 = 011101	43: A_B
G_B	39 = 100111	44: BIG
LA	33 = 100001	45: G_BL
CK	35 = 100011	46: LAC
_	26 = 011010	47: CK_
D	3 = 000011	48: _D
O	14 = 001110	49: DO
G	6 = 000110	50: OG

После таких несложных преобразований, сообщение вместо исходных 35 × 5 = 175 бит, стало занимать 6 × 5 + 19 × 6 = 144 бит. После преобразования к шестнадцатеричному виду заархивированное сообщение будет иметь вид (если длина итоговой последовательности бит не делится на 4, последовательность дополняется справа нулевыми битами)
06828370B00229C51F75369B767863683386
Процесс декодирования происходит аналогично. Единственным отличием является, то словарь заполняется в два этапа.

Данные	На выходе	Полная новая запись	Частичная новая запись	Комментарий
00000 = 0	A		27: A?
11010 = 26	_	27: A_	28: _?
00001 = 1	B	28: _B	29: B?
01000 = 8	I	29: BI	30: I?
00110 = 6	G	30: IG	31: G?
11100 = 28	_B	31: G_	32: _B?	далее используем 6-битные группы
001011 = 11	L	32: _BL	33: L?
000000 = 0	A	33: LA	34: A?
000010 = 2	C	34: AC	35: C?
001010 = 10	K	35: CK	36: K?
011100 = 28	_B	36: K_	37: _B?
010100 = 20	U	37: _BU	38: U?
011111 = 31	G_	38: UG	39: G_?
011101 = 29	BI	39: G_B	40: BI?
010011 = 19	T	40: BIT	41: T?
011010 = 26	_	41: T_	42: _?
011011 = 27	A_	42: _A	43: A_?
101000 = 40	BI	43: A_B	44: BI?
100111 = 39	G_B	44: BIG	45: G_B?
100001 = 33	LA	45: G_BL	46: LA?
100011 = 35	CK	46: LAC	47: CK?
011010 = 26	_	47: CK_	48: _?
000011 = 3	D	48: _D	49: D?
001110 = 14	O	49: DO	50: O?
000110 = 6	G	50: OG	51: G?

Некоторая проблема при декодировании возникает, когда новый код сразу оказывается в сообщении. Пусть мы расшифровываем сообщение ABABABA:

Данные	На выходе	Полная новая запись	Частичная новая запись	Комментарий
00000 = 0	A		27: A?
00001 = 1	B	27: AB	28: B?
11011 = 27	AB	28: BA	29: AB?
11101 = 29	AB?	29: AB?		что с этим делать?

Кажется, это неразрешимая ситуация. Мы знаем наперёд, запись 29 означает ABA, но как алгоритм узнает об этом? Заметим, что запись 29 состоит из записи 27 плюс символ, идущий следующим. Значит запись 29 оканчивается на «символ, идущий следующим». Но, так как эта запись посылается сразу, то она должно начинаться с «символа, идущего следующим», и поэтому она оканчивается тем же символом, что и начинается, в данном случае - A. Это позволяет определить, что запись 29 — это ABA.
Группа путешественников, совершавшая Кругопланетную экспедицию, сбилась с пути и попала на заброшенную станцию. На ее центральный компьютер постоянно приходило одно и тоже сообщение, однако программное обеспечение, отвечающее за разархивацию данных, по странному стечению обстоятельств не работало. Помогите путешественникам понять, что содержится в этом странном сообщении – напишите программу, которая его разархивирует (декодирует).

Формат ввода
В единственной строке записана последовательность шестнадцатеричных цифр, длиной не более 105 – заархивированное сообщение.
Формат вывода
Выведите исходное сообщение до архивации.

0