Description

在计算机科学中，正则表达式是一种用于文本搜索和字符串匹配的强大工具。在这个问题中，使用了简化版的正则表达式：

• 空字符串 是一个正则表达式，只有空字符串匹配它。

• 单个小写字母 c 是一个正则表达式，由单个字母 $c$ 组成的字符串匹配它。

• 点号 . 是一个正则表达式，由任意单个字母组成的字符串匹配它。

• 或运算：如果 $\alpha$ 和 $\beta$ 是正则表达式，那么 (\alpha|\beta) 是一个正则表达式，只有当字符串 $s$ 匹配 $\alpha$ 或 $s$ 匹配 $\beta$ 时，$s$ 才匹配它。

• 连接运算：如果 $\alpha$ 和 $\beta$ 是正则表达式，那么 (\alpha\beta) 是一个正则表达式，只有当字符串 $s = xy$，$x$ 匹配 $\alpha$ 且 $y$ 匹配 $\beta$ 时，$s$ 才匹配它。

• Kleene 星号：如果 $\alpha$ 是正则表达式，那么 (\alpha*) 是一个正则表达式，只有当字符串 $s$ 是空的或 $s = xy$，$x$ 非空且匹配 $\alpha$ 且 $y$ 匹配 $(\alpha*)$ 时，$s$ 才匹配它。换句话说，$s$ 由零个或多个字符串组成，每个字符串都匹配 $\alpha$。

括号可以省略，在这个问题中，Kleene 星号具有最高优先级，连接运算具有中等优先级，或运算具有最低优先级。因此 abc*|de 表示 (ab(c*))|(de)。

例如，字符串 abcabcab 匹配 a(bc|a)*ab，但字符串 abcbab 不匹配。

你的任务是找到匹配给定正则表达式 $E$ 并包含给定子串 $S$ 的最短字符串。

Input Format

输入文件的第一行包含正则表达式 $E$。输入文件的第二行包含子串 $S$（$1 \le |E|, |S| \le 10\,000$）。

字符串 $S$ 由小写英文字母组成。表达式 $E$ 由小写英文字母和特殊字符组成：点号 (.)、括号 (( 和 ))、管道符号 (|) 和星号 (*)。

Output Format

输出同时匹配 $E$ 并包含 $S$ 作为子串的最短可能字符串 $T$。如果没有这样的字符串，输出 NO。

字符串 $T$ 只能包含小写英文字母。

a.*b
bab

abab

(ab)*
bb

NO

Hint

时间限制：10 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。