|
Название задачи: Ну и имечко! . |
 |
Условие
В семье программистов родился ребенок. Папа-программист хочет назвать ребенка так, чтобы его имя подходило под шаблон P, а мама-программист настаивает на шаблоне M. Найдите самое короткое имя, удовлетворяющее обоим шаблонам, или сообщите, что такого имени не существует и семья находится на грани развода.Шаблон представляет собой последовательность букв русского алфавита (буква «ё» не используется) и специальных символов, которые имеют следующие значения:
| ? | любая буква | |
| * | любое (возможно нулевое) число букв | |
| [P] | любая буква из диапазона P | |
| [!P] | любая буква не из диапазона P | |
| {n} | предыдущий символ, повторенный ровно n раз | |
| {n;} | предыдущий символ, повторенный не менее n раз | |
| {n;m} | предыдущий символ, повторенный от n до m раз | |
| @ | предыдущий символ, повторенный не менее одного раза |
При этом 0 ≤ n ≤ m ≤ 10. Диапазон задается перечислением через запятуюсимволов и интервалов символов. Интервал символов записывается в виде a-b,
что означает любую букву, расположенную в алфавите между a и b
включительно.
Символы могут комбинироваться. Например, запись [а,о,е,у,и,ы,э-я]@ означает произвольную непустую последовательность гласных
(необязательно повторяющихся). Запрещается записывать подряд фигурные
скобки и символы @.
Входные данные
В первой строке входного файла записан шаблон папы, а во второй – шаблон
мамы. Длина каждого шаблона не превосходит 80 символов.
Выходные данные
Выведите в выходной файла кратчайшее имя ребенка, удовлетворяющее обоим
шаблонам, если такое имя существует. Имя ребенка должно состоять из букв
русского алфавита. Большие и маленькие буквы не различаются. В случае
нескольких возможных имен требуется вывести первое по алфавиту. Если
искомого имени не существует, выведите сообщение «NO SOLUTION».
Пример входного файла
?ик*т[а-о][л-р]*
В??тор*
Пример выходного файла
Виктор
Решение
Скачать архив тестов и решенийЭта задача решается аналогично предыдущей, но требует гораздо более тщательного программирования.
