P7064 [NWRRC 2014] Expression

在计算机科学中，正则表达式是一种用于文本搜索和字符串匹配的强大工具。在这个问题中，使用了简化版的正则表达式： - 空字符串 ` ` 是一个正则表达式，只有空字符串匹配它。 - 单个小写字母 `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$ 的最短字符串。

无

无

时间限制：10 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。