11986: 【原1986】Pattern Matching

题目

题目描述

author: xjia 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1986

Description

Ever heard of regular expressions? If not, familiar yourself with regular expressions by reading the wiki page for regular expression and some examples.

So you are now back from the wiki pages. In this task, you are required to implement a regex engine for a very simple variant of normal regex. The only metacharacters involved here are ^.?+*$. See the table below for detailed information.

Metacharacter(s)	Description
.	Normally matches any character except a newline.
?	Matches the preceding pattern element zero or one times.
+	Matches the preceding pattern element one or more times.
*	Matches the preceding pattern element zero or more times.
^	Matches the beginning of a line.
$	Matches the end of a line.

Note that there's only quantification in this simple regex language. No boolean "or" and no grouping. Take it easy and good luck!

Input Format

The first line is a valid regular expression. Following lines are the lines to match. Only 8-bit ASCII printable characters will appear in the input.

Output Format

For each line to match, output YES if the line can be matched, or NO if not.

Sample Input 1

a.+b
ab
aab
xabby
a   b
abcdb

Sample Output 1

NO
YES
YES
YES
YES

Sample Input 2

^a.+b
aabb
xabby
   aabbz
a a b beee
^aaabbb

Sample Output 2

YES
NO
NO
YES
NO

Sample Input 3

^a.+b$
aabb
xabby
aecdb
abcde
aabb$

Sample Output 3

YES
NO
YES
NO
NO

Limits

Time limit: 1000ms, memory limit: 30000kb.

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！