？？？？？？？？？？？

Question

c：匹配任意字母c

.：匹配任意的单个字符

^：匹配输入字符串的开头

$：匹配输入字符串的结尾

：匹配前一个字符的零个或者多个出现。例如 zo 可以匹配 z、zo、zoo、zooo

?：匹配前一个字符0次或一次。例如 zo? 可以匹配 z、zo

+：匹配前一个字符1次或多次。例如 zo+ 可以匹配 zo、zoo、zooo，但是不能匹配 z

输入

输入第一行为一个正则表达式的模式串，只包含大小写字母和以上字符。1 ≤ 串长 ≤ 20

输入第二行开始，每行一个字符串，只包含大小写字母。1 ≤ 串长 ≤ 100

输入以EOF结束，字符串的个数不超过100。

输出

对于输入的每个字符串，如果模式串可以匹配，输出“YES”，否则输出"NO"。

提示

1. ^最多只可能在最前出现一次

2. $最多只可能在最后出现一次

3. ?、*、+前一定是一个字母或者.

4. 请不要使用以“reg”为开头的变量名和函数名，否则可能导致Compile Error。

Answer 1

自己实现正则表达式引擎，画出状态图，写成有穷自动机就可以实现。