정규식과 부분 문자열

정규식은 문자열 검색과 대조에 쓰는 도구다. 이 문제에서는 다음 규칙으로 정의한 단순한 정규식만 다룬다.

• 빈 문자열은 정규식이다. 빈 문자열만 여기에 대응된다.
• 소문자 한 글자 c는 정규식이다. 그 글자 하나로 이루어진 문자열만 대응된다.
• 점 .은 정규식이다. 길이가 1인 문자열이면 어떤 소문자든 대응된다.
• 선택: α와 β가 정규식이면 (α|β)도 정규식이다. 문자열 s는 α에 대응되거나 β에 대응될 때만 여기에 대응된다.
• 이어붙이기: α와 β가 정규식이면 (αβ)도 정규식이다. s를 s = xy로 나누어 x가 α에, y가 β에 대응되게 할 수 있을 때만 s가 여기에 대응된다.
• 반복: α가 정규식이면 (α*)도 정규식이다. s가 빈 문자열이거나, s = xy로 나누어 x가 비어 있지 않으면서 α에 대응되고 y가 (α*)에 대응될 때만 s가 여기에 대응된다. 즉 s는 α에 대응되는 문자열을 0개 이상 이어붙인 것이다.

괄호는 생략할 수 있다. 우선순위는 반복이 가장 높고, 이어붙이기가 그다음이며, 선택이 가장 낮다. 그래서 abc*|de는 (ab(c*))|(de)와 같다.

예를 들어 abcabcab는 a(bc|a)*ab에 대응되지만 abcbab는 대응되지 않는다.

정규식 E와 문자열 S가 주어진다. E에 대응되면서 S를 부분 문자열로 포함하는 가장 짧은 문자열을 구하라.

첫째 줄에 정규식 E가, 둘째 줄에 문자열 S가 주어진다 ($1 \le |E|, |S| \le 2000$).

S는 영어 소문자로만 이루어진다. E는 영어 소문자와 특수문자 ., (, ), |, *로 이루어지며, 위 규칙에 맞는 올바른 정규식이다.

E에 대응되면서 S를 부분 문자열로 포함하는 가장 짧은 문자열 T를 출력한다. 길이가 가장 짧은 문자열이 여러 개면 그중 사전순으로 가장 앞서는 것을 출력한다. 그런 문자열이 없으면 NO를 출력한다.

T는 영어 소문자로만 이루어진다.