<PREV Problem:
NEXT>
Solved by 186 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Regular Expression II

Time limit = 3 second(s)

A given regular expression consists of a sequence of obligatory lexems and optional elements. Each optional element is a regular expression too. The regular expression has the following syntax:

regexp ::= ( lexem | '[' regexp ']' ) +

Lexem can be one of ascii characters except of square brackets.

For example, regular expression "a[b]" means "a" or "ab". Example of more complex regular expression:

abc[de[f]g][h]i[j]

You must give an answer whether the given string S matches against the given regular expression R. Maximal length of the string and regular expression does not exceed 1000 characters. The regualar expression is correct.

Input Two lines. The first contains S, the second contains R.

Output YES in case of matcing and NO in other case.

Input#1
[er[r]we]
erwe

Output#1
YES

Input#2
a[we[r[t[y[u]]]]]
awe

Output#2
YES

Input#3
a[we[r[t[y[u]]]]]
au

Output#3
NO


Author:

17 December 2003

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID = 23.20.13.165