P - Dancing stars on regular expression!
Editorial
/
Time Limit: 1 sec / Memory Limit: 256 MB
問題文
ここでは、以下の構文で表される文字列を "正規表現" と呼ぶ。
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 は存在しません。