表达式 - 题目

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

空字符串 "" 是一个正则表达式，仅匹配空字符串。
单个小写字母 c 是一个正则表达式，匹配由单个字母 c 组成的字符串。
点号 . 是一个正则表达式，匹配任意单个字母。
选择（Alternation）：如果 $\alpha$ 和 $\beta$ 是正则表达式，则 (α|β) 是一个正则表达式，字符串 $s$ 匹配它当且仅当 $s$ 匹配 $\alpha$ 或 $s$ 匹配 $\beta$。
连接（Concatenation）：如果 $\alpha$ 和 $\beta$ 是正则表达式，则 (αβ) 是一个正则表达式，字符串 $s$ 匹配它当且仅当 $s = xy$，$x$ 匹配 $\alpha$ 且 $y$ 匹配 $\beta$。
克莱尼星号（Kleene star）：如果 $\alpha$ 是正则表达式，则 (α*) 是一个正则表达式，字符串 $s$ 匹配它当且仅当 $s$ 为空，或 $s = xy$，$x$ 非空且匹配 $\alpha$，$y$ 匹配 (α*)。换句话说，$s$ 由零个或多个字符串组成，其中每个字符串都匹配 $\alpha$。

括号可以省略。在本题中，克莱尼星号的优先级最高，连接的优先级次之，选择的优先级最低。因此 abc*|de 意味着 (ab(c*))|(de)。

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

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

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

字符串 $S$ 由小写英文字母组成。正则表达式 $E$ 由小写英文字母和特殊字符组成：点号（.）、括号（( 和 )）、竖线（|）以及星号（*）。

输出匹配 $E$ 且包含 $S$ 作为子串的最短字符串 $T$。如果不存在这样的字符串，输出 NO。

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

a.*b
bab

abab

(ab)*
bb

NO

QOJ.ac