Декодирование префиксных кодов
(Время: 2 сек. Память: 16 Мб Сложность: 59%)
Кодом называют сопоставление C: Σ → Γ каждому символу некоторого алфавита Σ строк над некоторым (возможно другим) алфавитом Γ. В этой задаче Σ состоит из маленьких букв английского алфавита, а Γ = {0, 1}.
Код называют префиксным, если ни одно кодовое слово не является префиксом другого кодового слова. Например, код c('a') = 00, c('b') = 01, c('c') = 1 является префиксным, а код c('a') = 0, c('b') = 01 – нет.
Вам задан текст и строка, которая получается в результате кодирования этого текста некоторым префиксным кодом. Вам требуется восстановить код, который был использован для кодирования текста. Если возможных вариантов несколько, выведите любой.
Входные данные
Первая строка входного файла INPUT.TXT содержит заданный текст. Его длина не превышает 1000. Он состоит только из букв 'a'…'z' английского алфавита. Всего в тексте используется не более 10 различных букв.
Вторая строка содержит закодированную версию заданного текста. Гарантируется, что она была получена из текста кодированием его с использованием некоторого префиксного кода, длина каждого кодового слова в котором не превышает 10.
Выходные данные
В выходной файл OUTPUT.TXT выведите код, который мог быть использован для кодирования текста. Количество строк в выводе должно совпадать с количеством различных символов в заданном тексте.
Каждая строка должна содержать символ, после которого должен следовать пробел, а затем кодовое слово для этого символа.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | hello
0100111000 | e 001
h 01
l 1
o 000 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
