Описание
В семье программистов родился ребенок. Папа-программист хочет назвать ребенка так, чтобы его имя подходило под шаблон Р, а мама-программист настаивает на шаблоне М

Шаблон представляет собой последовательность букв русского алфавита (буква "ё" не используется) и специальных символов, которые имеют следующие значения:

?
*
[Р]
[!Р]
{п}
{п;}
{п;m}
@

любая буква
любое (возможно нулевое) число букв
любая буква из диапазона Р
любая буква не из диапазона Р
предыдущий символ, повторенный ровно n раз
предыдущий символ, повторенный не менее n раз
предыдущий символ, повторенный от n до m раз
предыдущий символ, повторенный не менее одного раза

При этом 0пт10. Диапазон задается перечислением через запятую символов и интервалов символов. Интервал символов записывается в виде а-b, что означает любую букву, расположенную в алфавите между а и b включительно

Символы могут комбинироваться. Например, запись [а,о,е,у,и,ы,э-я]@ означает произвольную непустую последовательность гласных (необязательно повторяющихся). Запрещается записывать подряд фигурные скобки и символы @

Задача
Найдите самое короткое имя, удовлетворяющее обоим шаблонам, или сообщите, что такого имени не существует и семья находится на грани развода


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

Выходные данные
Выведите в выходной файла кратчайшее имя ребенка, удовлетворяющее обоим шаблонам, если такое имя существует. Имя ребенка должно состоять из букв русского алфавита. Большие и маленькие буквы не различаются. В случае нескольких возможных имен требуется вывести первое по алфавиту. Если искомого имени не существует, выведите сообщение "NO SOLUTION".


Например:

TEMPLATE.IN

?ик*т[а-о][л-р]*
В??тор*


TEMPLATE.OUT
Виктор





Идеи
Синтаксический анализ, динамическое программирование.

Комментарии

Эта задача решается аналогично предыдущей, но требует гораздо более тщательного программирования





Решение
Авторское решение не представлено


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