Условие:
Эльринг – главный герой, попавший в цифровой мир Алгоритмия. В этом мире со-общения передаются с помощью особых магических последовательностей из двух стихий: «Свет» (0) и «Тьма» (1).
Маги всех времен договорились использовать префиксный код (Священный Прин-цип Фано), чтобы ни одно заклинание не начиналось так же, как другое. Благодаря этому расшифровка всегда однозначна.
Пример корректного кодирования: a → 0, b → 11, c → 10 (ни один код не является началом другого, поэтому строка abaca превращается в 0110100).
У каждого мага своя таблица кодирования. Но случилась беда: таблица была утеряна. Однако сохранилось два артефакта: исходное сообщение (строка из букв английского алфа-вита) и закодированное сообщение (строка из Света и Тьмы – символов 0 и 1).
Ваша задача — восстановить таблицу кодирования по этим данным.
Формат входных данных
Первая строка содержит исходное сообщение – строка, состоящая только из строчных английских букв (a–z). Длина строки не превосходит 2000.
Во второй строке находятся закодированное сообщение – строка, состоящая только из символов 0 и 1. Длина строки не превосходит 2000.
Гарантируется, что:
– закодированное сообщение получено из исходного с помощью некоторой таблицы кодирования;
– используемая таблица кодирования удовлетворяет префиксному свойству;
– коды существуют для всех букв, встречающихся в исходном сообщении, и только для них;
– входные данные корректны (существует хотя бы одна таблица, удовлетворяющая условию).
Формат выходных данных
Необходимо вывести таблицу кодирования в следующем формате:
– Каждая строка таблицы содержит: одну строчную английскую букву, затем ровно один пробел, затем её код – непустая строка из символов 0 и 1.
– Строки таблицы должны следовать в порядке первого появления букв в исходном сообщении.
– Каждая буква выводится ровно один раз (даже если встречается в исходном сооб-щении несколько раз).
– Если существует несколько возможных таблиц кодирования, выведите любую.
