• Шаблон с ? и *
  PATTERN
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

Описание
Шаблоном называется строка, состоящая из английских букв (а, ..., 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. 
 

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