|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|10 초||256 MB||1||1||1||100.000%|
In computing, regular expressions is a powerful tool for text search and string matching. In this problem a simplified version of regular expressions is used:
Parentheses can be omitted, in this problem Kleene star has the highest priority, concatenation has medium priority and alternation has lowest priority. Thus “abc*|de” means “(ab(c*))|(de)”.
For example, string “abcabcab” matches “a(bc|a)*ab”, but string “abcbab” does not.
Your task is to find the shortest string that matches the given regular expression E and contains the given substring S.
The first line of the input file contains the regular expression E. The second line of the input file contains the substring S (1 ≤ |E| , |S| ≤ 10 000).
String S consists of lowercase English letters. Expression E consists of lowercase English letters and special characters: dots (‘.’), parentheses (‘(’ and ‘)’), pipes (‘|’), and asterisks (‘*’).
Output the shortest possible string T that both matches E and contains S as substring. If there are no such strings, output “NO”.
The string T should contain only lowercase English letters.