Описание
Шаблоном называется строка, состоящая из английских букв (а, ..., z, А, ..., Z) и символов "?" и "*". Каждый из символов "?" разрешается заменить на одну произвольную букву, а каждый из символов "*" - на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

Задача
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблона, либо выдать сообщение, что такой строки не существует


Входные данные
Заданные шаблоны записаны в первых двух строках входного файла. Длина каждого шаблона не превосходит 80 символов

Выходные данные
В выходной файл следует вывести строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "Строки не существует!"


Например:

PATTERN.IN
А*


PATTERN.OUT
АВ





Комментарии
Пусть нам заданы два шаблона S[1..M] и T[1..N]. Обозначим через F(i,j) любую строку минимальной длины, удовлетворяющую шаблонам S[1..i] и T[1..j]. Если такой строки нет, то в F(i,j) будет стоять специальная пометка, говорящая об этом

Вычисляем значения F(i,j) в порядке возрастания i, а при равных i - в порядке возрастания j. Возможны следующие ситуации (мы считаем, что i,j>0, разбор граничных случаев проведите самостоятельно):

  • S[i] и T[j] - буквы. Если они совпадают, то в качестве F(i,j) берем значение F(i-1,j-1) с дописанной в конце этой буквой. Если в F(i-1,j-1) стоит пометка "строки не существует", то аналогичная пометка ставится и в F(i,j). В случае несовпадения букв S[i] и T[j] нужная строка также не существует

  • S[i] и T[j] - буква и символ "?" или два символа "?". Поступаем точно так же, как и в предыдущей ситуации, однако случая несовпадения букв из-за наличия "?" здесь быть не может

  • S[i] - символ "*", T[j] - буква или символ "?". Выбираем наиболее короткое среди значений F(i-1,j) и F(i,j-1) с дописанной к нему буквой T[j] (или любой буквой, если T[j] есть символ "?")

  • S[i] - буква или символ "?", T[j] - символ "*". Поступаем аналогично ситуации 3

  • S[i] и T[j] - два символа "*". В этой ситуации в качестве F(i,j) берем наиболее короткое из значений F(i,j-1) и F(i-1,j)

Упражнение
Решите задачу, храня в F(i,j) не кратчайшую строку, а только ее длину (или пометку "-1", если такой строки не существует)





Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+} 
{$M 64000,0,655360} 
  
program pattern; 
const 
  inf=32000; 
var 
  S1,S2:String
  L,H1,H2:Array[0..80,0..80] of Integer; 
  Min1,Min2:Array[1..80,0..80] of Byte; 
 
Procedure Input; 
  Var 
    F:Text; 
    S:String
  Begin 
    Assign(F,'pattern.in'); ReSet(F); 
    Readln(F,S1); Readln(F,S2); Close(F); 
  End
 
Procedure Init; 
  Var 
    I,J,K:Integer; 
  Begin 
    For I:=0 to 80 do 
      For J:=0 to 80 do 
        L[i,j]:=-1; 
    L[0,0]:=0; 
    For I:=1 to Length(S1) do 
    Begin 
      K:=0; 
      For J:=I to Length(S1) do 
      Begin 
        if S1[j]<>'*' then Inc(K); 
        Min1[i,j]:=K; 
      End
    End
    For I:=1 to Length(S2) do 
    Begin 
      K:=0; 
      For J:=I to Length(S2) do 
      Begin 
        if S2[j]<>'*' then Inc(K); 
        Min2[i,j]:=K; 
      End
    End
  End
 
Function M(p,i,j:Integer):Integer; 
  Begin 
    if i>j then 
      M:=0 
    else 
      Case p of 
        1: M:=Min1[i,j]; 
        2: M:=Min2[i,j]; 
      End
  End
 
Function GetM(p,i,j:Integer):String
  Var 
    k,l:Integer; 
    S:String
    Ch:Char; 
  Begin 
    S:=''; 
    For k:=i to j do 
    Begin 
      Case p of 
        1: Ch:=S1[k]; 
        2: Ch:=S2[k]; 
      End
      if Ch='?' then Ch:='@'; 
      if Ch<>'*' then S:=S+Ch; 
    End
    GetM:=S; 
  End
 
Function CalcLength(a,b:Integer):Integer; 
  Var 
    I,J:Integer; 
  Begin 
    if L[a,b]=-1 then 
    Begin 
      L[a,b]:=inf; 
      if (a>0) and (s1[a]='*') then 
      Begin 
        For I:=b downto 0 do 
          if L[a,b]>CalcLength(a-1,i)+M(2,i+1,b) then 
          Begin 
            L[a,b]:=CalcLength(a-1,i)+M(2,i+1,b); H1[a,b]:=a-1; H2[a,b]:=i; 
          End
      End Else 
      if (b>0) and (s2[b]='*') then 
      Begin 
        For I:=a downto 0 do 
          if L[a,b]>CalcLength(i,b-1)+M(1,i+1,a) then 
          Begin 
            L[a,b]:=CalcLength(i,b-1)+M(1,i+1,a); H1[a,b]:=i; H2[a,b]:=b-1; 
          End
      End Else 
      if (a>0) and (b>0) and ((s1[a]='?') or (s2[b]='?') or (s1[a]=s2[b])) then 
      Begin 
        L[a,b]:=CalcLength(a-1,b-1)+1; 
        H1[a,b]:=a-1; H2[a,b]:=b-1; 
      End
    End
    CalcLength:=L[a,b]; 
  End
 
Procedure WriteM(a,b,c:Integer); 
  Begin 
    Write(GetM(a,b,c)); 
  End
 
Procedure WriteStr(a,b:Integer); 
  Var 
    I:Integer; 
  Begin 
    if (a>0) and (s1[a]='*') then 
    Begin 
      I:=H2[a,b]; 
      WriteStr(H1[a,b],H2[a,b]); 
      WriteM(2,i+1,b); 
    End Else 
    if (b>0) and (s2[b]='*') then 
    Begin 
      I:=H1[a,b]; 
      WriteStr(H1[a,b],H2[a,b]); 
      WriteM(1,i+1,a); 
    End Else 
    if (a>0) and (b>0) and ((s1[a]='?') or (s2[b]='?') or (s1[a]=s2[b])) then 
    Begin 
      WriteStr(H1[a,b],H2[a,b]); 
      if s1[a]<>'?' then 
        Write(s1[a]) 
      else 
      if s2[b]<>'?' then 
        Write(s2[b]) 
      else 
        Write('@'); 
    End
  End
 
Procedure Print; 
  Var 
    L:Integer; 
    S:String
  Begin 
    assign(output, 'pattern.out'); 
    reWrite(output); 
 
    L:=CalcLength(Length(s1),Length(s2)); 
    if L>=inf then 
      WriteLn('‘ва®ЄЁ ­Ґ бгйҐбвўгҐв!') 
    else 
    Begin 
      WriteStr(Length(S1),Length(S2)); 
    End
  End
 
Begin 
  Input; 
  Init; 
  Print; 
  close(output) 
End

 


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