Олимпиадный тренинг

Задача . Сжатие текста


Задача

Темы:
Архиватором называется программа, предназначенная для сжатия данных за счет удаления избыточной информации. В этой задаче вашей целью является разработка простейшего архиватора текстов на русском языке.  В таких текстах многие знаки стандартной таблицы символов не встречаются, поэтому они могут быть использованы для замены часто повторяющихся последовательностей символов. 
 
Заданы последовательности, которые могут быть заменены некоторыми символами английского алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти последовательности могут накладываться друг на друга, результат сжатия существенно зависит от порядка замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей длины.
 
Входные данные
В первой строке входного файла задано целое число R - количество заменяемых последовательностей и целое число N - количество строк в исходном тексте (1<=N<=1000). Далее следуют R пар строк, описывающих возможные замены. Первая строка каждой пары содержит заменяемую последовательность, а вторая - заменяющий символ, являющийся большой или маленькой английской буквой. Различным заменяемым последовательностям соответствуют разные английские буквы (большие и маленькие буквы различаются). В следующих N строках записан текст,  подлежащий сжатию. В этом тексте, также как и в заменяемых последовательностях, отсутствуют буквы английского алфавита.
 
Выходные данные
В выходной файл вывести заархивированный текст.
 
Примечания
Символы перевода строки не заменяются (т.е. замены возможны только внутри строк). Длина каждой строки входного файла не превосходит 255 символов.
 
Пример входного файла
8 10
рхиватор
b
замен
D
ены
F
зам
G
быт
h
про
d
сжат
f
ом называется
g
Архиватором называется программа, предназначенная для сжатия данных за счет удаления 
избыточной информации. В этой задаче вашей целью является разработка простейшего 
архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы 
символов не встречаются, поэтому они могут быть использованы для замены часто 
повторяющихся последовательностей символов. 
 
Заданы последовательности, которые могут быть заменены некоторыми символами английского 
алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти 
последовательности могут накладываться друг на друга, результат сжатия существенно зависит 
от порядка замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей длины.
 
Пример выходного файла
Аbg dграмма, предназначенная для fия данных за счет удаления 
изhочной информации. В этой задаче вашей целью является разработка dстейшего 
аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы 
символов не встречаются, поэтому они могут hь использованы для Dы часто 
повторяющихся последовательностей символов. 
 
Заданы последовательности, которые могут hь DF некоторыми символами английского 
алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти 
последовательности могут накладываться друг на друга, результат fия существенно зависит 
от порядка D. Ваша задача состоит в том, чтобы получить fый текст наименьшей длины.
 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя