logo AlgoBeat OnlineJudge
登录 注册

#141. 【模板】正则表达式

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

给出一个非空的正则表达式和一个字符串,求该字符串是否能匹配该正则表达式。

这个正则表达式可能含有:

  • 基本元素:空串(输入中不体现);单个小写字母(例如 a),匹配小写字母 a

  • 运算符

    • 连接(例如 ab):ab 匹配可以表示成一个与 a 匹配的串与一个与 b 匹配的串相连接的串(其中 a 表示一个正则表达式,下同)。
    • (例如 a|b):a|b 匹配与 ab 中至少一个匹配的串。
    • 闭包(例如 a*):a* 匹配零个或多个与 a 匹配的串的连接。
    • 正闭包(例如 a+):a+ 匹配一个或多个与 a 匹配的串的连接。
    • 括号(例如 (a))。

其中连接和或是二元运算符,闭包和正闭包是一元运算符。

所有运算符都是左结合的,即同等优先级的运算顺序从左到右。
闭包和正闭包的优先级最高,连接次之,或的优先级最低。

输入格式

多组数据,每组数据两行:

  • 第一行是一个非空正则表达式,保证符合上述定义,但可能出现多余括号。保证不出现空括号。
  • 第二行是一个由小写字母组成的非空字符串。

输出格式

对于每组数据,如果正则表达式能匹配该字符串,输出一行 Yes,否则输出一行 No

样例

输入:

aa
a
a*
aa
a+
a
c*a*b
aab
ab*a
bbb
a(a|b+)*a
aa
a(a|b+)*a
aababba
a(a|cb+)*a
aca
a(a|cb+)*a
acbbbaacba
a(a|cb+)*a
acbbbaacb
((a*))
aa

输出:

No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes

数据范围与提示

  • 对于 的数据,正则表达式仅由小写字母、*+ 组成。
  • 对于 的数据,每个正则表达式和字符串长度不超过