|
Название задачи: Шаблоны с ? и * . |
 |
Условие
Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.Имеются два шаблона. Требуется найти строку минимальной длины,
которая удовлетворяет обоим шаблона, либо выдать сообщение, что такой
строки не существует.
Входные данные
Заданные шаблоны записаны в первых двух строках входного файла. Длина
каждого шаблона не превосходит 80 символов.
Выходные данные
В выходной файл следует вывести строку минимальной длины,
удовлетворяющую обоим шаблонам, либо сообщение «Строки не
существует!»
Пример входного файла
A*
*B
Пример выходного файла
AB
Решение
Скачать архив тестов и решенийПусть нам заданы два шаблона 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, если такой строки не существует).
