Шаблоны

Ограничение времени: 1 секунды
Ограничение памяти: 5000КБ

Условие задачи

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

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

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

Пример входных и выходных данных
INPUT
A*
*B
OUTPUT
2

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

Мое решение на Delphi

program shablon; {$APPTYPE CONSOLE} const p=18000; max=45; var s1,s2:string; l,h1,h2:array[0..max,0..max] of integer; min1,min2:array[1..max,0..max] of byte; i,j,k,l2:integer; 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 calclength(a,b:integer):integer; var i:integer; begin if l[a,b]=-1 then begin l[a,b]:=p; 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=′*′) 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=′?′) or (s1[a]=s2)) 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; begin readln(s1); readln(s2); for i:=0 to max do for j:=0 to max 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; l2:=calclength(Length(s1),Length(s2)); if l2>=p then write(′NO STRING′) else write(l2); readln; end.