|
Название задачи: Сжатие текста . |
 |
Условие
Архиватором называется программа, предназначенная для сжатия данных за счет удаления избыточной информации. В этой задаче вашей целью является разработка простейшего архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы символов не встречаются, поэтому они могут быть использованы для замены часто повторяющихся последовательностей символов. Заданы последовательности, которые могут быть заменены некоторыми
символами английского алфавита, а также исходный текст, который следует
сжать. Поскольку в исходном тексте эти последовательности могут
накладываться друг на друга, результат сжатия существенно зависит от порядка
замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей
длины.
Входные данные
В первой строке входного файла заданы целое число 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ый текст наименьшей длины.
Решение
Скачать архив тестов и решенийДостаточно рассмотреть задачу архивирования одной строки S[1..N] длины N. Обозначим через Fk минимально возможную длину архива для первых k символов этой строки (F0 = 0). Пусть значения F0 , F1 , ..., Fk-1 уже известны. Очередное значение Fk вычисляется следующим образом.
Рассмотрим подстроку из первых k символов архивируемой строки – S[1..k]. Попытаемся применить к ее «хвосту» все разрешенные варианты замен. Каждая замена, которую уместно использовать, позволяет закодировать последние несколько символов S[k-i+1..k], а минимальная длина архива для подстроки S[1..k-i] равна F k-i и уже известна. Теперь из всех вариантов уместных замен выбираем тот, который дает минимальную суммарную длину (не забывая проверить и случай, при котором последняя буква берется без архивирования). Минимально возможной длиной архива для всей строки является значение FN , а способ архивирования, приводящий к такой длине, легко восстанавливается по найденным значениям Fk .
