「模板」正则表达式
测试数据来自 system/1017
Description
给出一个非空的正则表达式和一个字符串,求该字符串是否能匹配该正则表达式。
这个正则表达式可能含有:
基本元素:
- 空串,输入中不体现;
- 单个小写字母(例如
a
),a
匹配小写字母a
,这里a
表示小写字母a
。
运算符:
- 连接(例如
ab
),ab
匹配可以表示成一个与a
匹配的串与一个与b
匹配的串相连接的串,这里a
表示一个正则表达式,下同。 - 或(例如
a|b
),a|b
匹配与a
和b
中至少一个匹配的串。 - 闭包(例如
a*
),a*
匹配零个或多个与a
匹配的串的连接。 - 正闭包(例如
a+
),a+
匹配一个或多个与a
匹配的串的连接。 - 括号(例如
(a)
)
其中连接和或是二元运算符,闭包和正闭包是一元运算符。
所有运算符都是左结合的,即同等优先级的运算顺序从左到右。
闭包和正闭包的优先级最高,连接次之,或的优先级最低。
Format
Input
多组数据,每组数据两行:
第一行是一个非空正则表达式,保证符合上述定义,但可能出现多余括号。保证不出现空括号。
第二行是一个由小写字母组成的非空字符串。
Output
对于每组数据,如果正则表达式能匹配该字符串,输出一行 Yes
,否则输出一行 No
。
Sample 1
Input
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
Output
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Limitation
Data
对于 \(40\%\) 的数据,正则表达式仅由小写字母,*
和 +
组成。
对于 \(100\%\) 的数据,每个正则表达式和字符串长度不超过 \(100\)。
Time and Space
1s, 125MB.
Source
loj #118
update by Shuchong
信息
- ID
- 1028
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者