Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Декодирование префиксных кодов

(Время: 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.TXTOUTPUT.TXT
1hello
0100111000
e 001
h 01
l 1
o 000

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 A. Маги
 B. Болото
 C. Последовательность
 D. Военная академия
 E. Рейсы во времени
 F. Части многоугольника
 G. Декодирование префиксных кодов
 H. Гена атакует

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru