eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Выражение

Выражение

Ліміт часу 5 секунд
Ліміт використання пам'яті 256 MiB

При вычислении регулярные выражения являются мощным инструментом для текстового поиска и сопоставления строк. В этой задаче используется упрощенная версия регулярных выражений:

  • Пустая строка "" является регулярным выражением, и только пустая строка соответствует ей.

  • Одна строчная буква "c" является регулярным выражением. Строка, состоящая из одной буквы c, соответствует ему.

  • Точка "." является регулярным выражением. Строка, состоящая из любой единственной буквы, соответствует ему.

  • Чередование: если a и b регулярные выражения, то "(a|b)" также регулярное выражение, строка s соответствует ему, если только s соответствует a или b.

  • Конкатенация: если a и b регулярные выражения, то "(ab)" также регулярное выражение, строка s соответствует ему только если s = xy, x соответствует a и y соответствует b.

  • Звезда Клини: если a регулярное выражение, то "(a\*)" также регулярное выражение, строка s соответствует ему только если s пусто или s = xy, x непусто и соответствует a и y соответствует (a\*). Другими словами, s состоит из нуля или более строк, каждая из которых соответствует a.

Скобки можно опустить, в этой задаче звезда Клини имеет наивысший приоритет, конкатенация имеет средний приоритет и чередование имеют самый низкий приоритет. То есть "abc\*|de" означает "(ab(c\*))|(de)".

Например, строка "abcabcab" соответствует "a(bc|a)\*ab", но строка "abcbab" нет.

Вам следует найти кратчайшую строку, которая соответствует данному регулярному выражению E, и содержит заданную подстроку S.

Вхідні дані

Первая строка содержит регулярное выражение E. Вторая строка содержит подстроку S (1 ≤ |E|,|S| ≤ 10 000).

Строка S состоит из прописных латинских букв. Выражение E состоит из прописных латинских букв и специальных символов: точки ('.'), скобок ('(' и ')'), трубы ('|') и звездочек ('\*').

Вихідні дані

Выведите кратчайшую строку T, которая соответствует E и содержит S как подстроку. Если такой строки не существует, вывести "No".

Строка T должна содержать только прописные латинские буквы.

Приклад

Вхідні дані #1
a.*b
bab
Вихідні дані #1
abab
Вхідні дані #2
(ab)*
bb
Вихідні дані #2
No
Джерело 2014 ACM NEERC, Northern Subregion, November 8, Problem E