#P2003. ACSL 2015-2016 Junior Division Contest #4 ACSL Reg Exp
-
ID: 929
Type: Default
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 1
Uploaded By:
ZihanShen
Tags> ACSL 2015-2016 Junior Division Contest #4 ACSL Reg Exp
PROBLEM DESCRIPTION
Regular Expressions and FSA is one of the ACSL categories that is not tested in the Junior Division. However it is being used here as a programming problem to show how a long string or multiple strings can be written in condensed format. The concept of regular expressions was first formalized by Stephen Kleene in the 1950s. The following operations will be used:
| Operator | Meaning & Examples |
|---|---|
| ? |
Indicates the preceding element appears zero or one time. Example: colou?r matches color and colour. |
| * |
Indicates the preceding element appears zero or more times. Example: ab*c matches ac, abc, abbc, abbbc, etc. |
| + |
Indicates the preceding element appears one or more times. Example: ab+c matches abc, abbc, abbbc, etc., but not ac. |
INPUT FORMAT
There will be lines of input. The first line will contain character strings. The last lines will contain a valid regular expression string. Each regular expression will have no more than characters and no more than two operators.
OUTPUT FORMAT
For each regular expression print all the character strings that are matches. If none match,
then print NONE. # is used here to represent the empty string.
SAMPLE
INPUT #1
#, a, aa, aaa, ab, abb, aabb, aaab, abbb, b
a?b
a*b
a+b
a*b+
a?b+
OUTPUT #1
ab, b
ab, aaab, b
ab, aaab
ab, abb, aabb, aaab, b, abbb
ab, abb, abbb, b