<ПРЕД Задача:
СЛЕД>
Задачу решили 37 пользователей: defrager, zloy_mipt, Jacob, ilyakor, Kuznetsov_S, WsemirZ, Ravent, UdH-WiNGeR, JohnJones_001, regal, MIKseR, dan, DmitrievVladimir814, gafrustam814, M_A_X, risinka_814, yura814, WinZib, Robin_Hood, coolzero814, Fat, abortmozga.ru, Romka, topspin, RAVEman, fetetriste, vi002, plantator, vitar, Dest, karakurt25, checkil, oleg.dudrov, ripatti, mikelan, adamant, dzhavaharnal.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Архиватор

Time limit = 1 секунд(ы)

Архиватором называется программа, предназначенная для сжатия данных за счет удаления избыточной информации. В этой задаче вашей целью является разработка простейшего архиватора текстов. В текстах многие знаки стандартной таблицы символов не встречаются, поэтому они могут быть использованы для замены часто повторяющихся последовательностей символов. Задан исходный текст и последовательности, которые могут быть заменены некоторыми символами, не встречающимися в тексте Поскольку в исходном тексте эти последовательности могут накладываться друг на друга, результат сжатия существенно зависит от порядка замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей длины.

Вход В первой строке входного файла заданы целое число R — количество заменяемых последовательностей и целое число N — количество строк в исходном тексте (1 ≤ N ≤ 1000). Далее следуют R пар строк, описывающих возможные замены. Первая строка каждой пары содержит заменяемую последовательность, а вторая заменяющий символ, являющийся большой или маленькой английской буквой. В следующих N строках записан текст, подлежащий сжатию.

Выход Сжатый текст

Вход#1
3 2
абв
A
где
B
бвэюягд
C
абвэюягде
гдеабв
Выход#1
аCе
BA

Автор:
Особенности национальных задач по информатике
2000

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 18.232.51.69