• Ну и имечко!
  TEMPLATE
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

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

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

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

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

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


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

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


Например:

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

TEMPLATE.OUT
Виктор





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

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





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

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