← 返回题目列表

AtCoder · ttpc2015_p

P. 正则表达式上跳舞的星星!

中文机器翻译题面 查看原题

問題文

这里,使用以下语法表达的字符串被称为“正则表达式”。

e ::= a...a | (e_1+e_2) | (e_1;e_2) | *(e_1) | !(e_1)

但是, 运算前设定中包含的a...a 是一个字符 a 可以得到第 1 表示可以通过多次重复来表示的字符串。 由

正規表現 e 表示的一组字符串 L(e) 归纳定义如下。

L(a...a) = \{a...a\}
       - 例えば、L(aa) = \{aa\}, L(aaa) = \{aaa\}。
L((e_1+e_2)) = L(e_1) ∪ L(e_2)
       - L(e_1) に属する または L(e_2) に属する 文字列 の集合。
L((e_1;e_2)) = L(e_1)L(e_2) = \{ w_1 w_2 | w_1 \in L(e_1), w_2 \in L(e_2) \}
       - L(e_1) に属する文字列 と L(e_2) に属する文字列 をつなげた文字列の集合。
L(*(e_1)) = L(e_1)^* = \{ε\} ∪ \{w_1 | w_1 \in L(e_1)\} ∪ ... ∪ \{w_1 ... w_n | w_1,...,w_n \in L(e_1)\} ∪ ...
       - L(e_1) に属する文字列 を 有限回つなげた (0 回の場合も含む) 文字列の集合。
L(!(e_1)) = Σ^* - L(e_1)
       - L(e_1) に属さない文字列 の集合。

但是, 运算前设定中包含的Σ^* 是整个字符串集 代表 \{ε(空の文字列),a,aa,aaa,...\} = ( a を有限個つなげた文字列の集合) 。

另外,在下面的句子中,“正则表达式没有!”是什么意思?意思是? ! 指的是没有出现的正则表达式,“不带*的正则表达式”是 指不出现 * 的正则表达式。

现在,正则表达式不带 ! *没有满足 S 。 对于

L(S) = L(T) 的正则表达式 判断 T 是否存在。 在线输入


入力

输入是按以下格式从标准输入给出的。

N
S
  • 1 行中,2 输入到行中 S 字符串长度 N(1 ≦ N ≦ 4000)。
  • 2 行包含一个表示不带 ! 的正则表达式的字符串。 如果 S 。 表示

出力

L(S) = L(T) 的正则表达式 判断 T 存在, 如果 YES 请输出

L(S) = L(T) 的正则表达式 判断 T 不存在, 在一行上输出 NO 请输出


入力例1

6
(a+aa)

出力例1

YES

T = (a+aa) 。


入力例2

17
(*(aa)+(*(aa);a))

出力例2

YES

T = (!(a)+a) 。


入力例3

14
(*(aa)+*(aaa))

出力例3

NO

L(S) = L(T) 的正则表达式 判断 T 不存在。