Вираз#7496
При обчисленні регулярні вирази є потужним інструментом для текстового пошуку та зіставлення рядків. У цій задачі використовується спрощена версія регулярних виразів:
Порожній рядок "" є регулярним виразом, і тільки порожній рядок відповідає йому.
Одна велика літера "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
Приклад 2