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

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


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

Выходные данные
В выходной файл вывести заархивированный текст

Примечания
Символы перевода строки не заменяются (т.е. замены возможны только внутри строк). Длина каждой строки входного файла не превосходит 255 символов


Например:

COMPRESS.IN
8 10
рхиватор
b
замен
D
ены
F
зам
G
быт
h
про
d
сжат
f
ом называется
g
Архиватором называется программа, предназначенная для сжатия данных за счет удаления
избыточной информации. В этой задаче вашей целью является разработка простейшего
архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы
символов не встречаются, поэтому они могут быть использованы для замены часто
повторяющихся последовательностей символов.

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


COMPRESS.OUT
А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] равна Fk-i и уже известна. Теперь из всех вариантов уместных замен выбираем тот, который дает минимальную суммарную длину (не забывая проверить н случай, при котором последняя буква берется без архивирования). Минимально возможной длиной архива для всей строки является значение FN, а способ архивирования, приводящий к такой длине, легко восстанавливается по найденным значениям Fk





Решение

{$A+,B-,D+,E+,F-,G-,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+} 
{$M 65520,0,655360} 
 
program compress;
const
rmax=52; 
var n,r:integer; 
    p:array[1..rmax] of record 
      c:char; 
      s:string
      end
    a:array[0..255] of byte; 
    b:array[0..255] of byte; 
    tnum:integer; 
    s:string
 
procedure init; 
  var i:integer; 
      c:char; 
  begin 
  assign(input,'compress.in'); 
  reset(input); 
  assign(output,'compress.out'); 
  rewrite(output); 
  readln(r,n); 
  for i:=1 to r do begin 
    readln(p[i].s); 
    readln(p[i].c); 
    end
end
 
procedure work; 
  var i,j:byte; 
      q:string
      w:byte; 
  begin 
  fillchar(a,sizeof(a),0); 
  a[0]:=1; 
  b[0]:=0; 
  for i:=1 to length(s) do begin 
    a[i]:=a[i-1]+1; 
    b[i]:=0; 
    for j:=1 to r do begin 
      w:=length(p[j].s); 
      if w<=i then 
        if a[i-w]+1 then 
          if copy(s,i-w+1,w)=p[j].s then begin 
             a[i]:=a[i-w]+1; 
             b[i]:=j; 
             end
      end
  end
  q:=''; 
  i:=length(s); 
  while i<>0 do 
    if b[i]=0 then begin 
       q:=s[i]+q; 
       dec(i); 
       end 
    else begin 
       q:=p[b[i]].c+q; 
       i:=i-length(p[b[i]].s); 
       end
  writeln(q); 
end
 
BEGEN 
init; 
for tnum:=1 to n do begin 
  readln(s); 
  work; 
  end
close(input); 
close(output); 
END


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