시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 256 MB | 3 | 2 | 2 | 66.667% |
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.
a.*b bab
abab
(ab)* bb
NO