» Главная
eXcode.ru » Статьи » Задачи » С решениями
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 5





Шаблоны






Ограничение времени: 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.
К началу статьи





Добавил: LedWormДата публикации: 2005-06-02 17:02:58
Рейтинг статьи:3.00 [Голосов 5]Кол-во просмотров: 10871

Комментарии читателей

Всего комментариев: 3

2017-09-21 12:49:50
qElenaer
Мы платим за лайки! - Выплаты по требованию!

Наш сервис предоставляет настоящие лайки на фото заказчиков, которые готовы платить за качество.
Именно для этого мы и набираем удалённых сотрудников, которые будут выполнять работу, то есть ставить лайки и зарабатывать за это деньги.
Чтобы стать нашим удалённым сотрудником и начать ставить лайки, зарабатывая при этом 45 рублей за 1 поставленный лайк,
Вам достаточно просто зарегистрироваться на нашем сервисе. > oplata-vklike.tk <
Вывод заработанных средств ежедневно в течении нескольких минут.

2011-11-03 13:10:16
123
Напиши решение на PASCALE

2011-11-03 13:10:03
123
Напиши решение на PASCALE
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Каким ICQ-клиентом вы пользуетесь?
Стандартным ICQ - клиентом.
11% (23)
Miranda 'ой
13% (29)
крысой - &RQ
5% (10)
Своим собственным :)
4% (8)
Не пользуюсь, так как сижу на модеме :(
1% (3)
Не пользуюсь, мне и так хорошо ...
6% (13)
Qip'ом
56% (121)
Другим
4% (8)

Проголосовало: 215
Звонок по телефону: "Включи асю!"
Включаю асю, сообщение: "Посмотри почту!"
Смотрю почту, письмо: "Позвони мне!"
Звоню, слышу: "Включи асю!"
Рейтинг: 5/10 (6)
Посмотреть все анекдоты