Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайт |
Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
Входные данные
Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.
Выходные данные
Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение «No solution!»
Пример
| Входные данные | Выходные данные |
| A* | AB |
Здесь ДП f[i][j] - минимальная длина строки, удовлетворяющей первым i символам первого шаблона и первым j символам второго шаблона. Потом уже по готовому массиву f можно восстановить ответ.