#P2011. ACSL 2015-2016 Senior Division Contest #4 ACSL ACSL Reg Exp
-
ID: 925
Type: Default
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 2
Uploaded By:
ZihanShen
Tags> ACSL 2015-2016 Senior Division Contest #4 ACSL ACSL Reg Exp
Regular Expressions is one of the ACSL categories that is usually only tested at the ACSL Invitational All-Star Contest. 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 are used:
| ˙ | Matches any single character. Ex: a.c matches aac, abc, acc, adc, a#c, a4c, …etc. |
| [ ] | Matches a single character contained within the brackets. Ex: [abc] matches a, b, or c. |
| [^] | Matches any single character not contained within the brackets. [^abc] matches any character other than a, b, or c. |
| * | Matches the preceding character zero or more times. Ex; a*b matches b, ab, aab, aaab, …etc. |
| {m,n} | Matches the preceding character at least m but not more than n times. Ex: a{3,5} matches aaa, aaaa, or aaaaa. |
INPUT FORMAT
There will be 6 lines of input. The first line will contain 10 character strings. The last 5 lines will contain a valid regular expression string. Each regular expression will have at most two (2) operators.
OUTPUT FORMAT
For each regular expression print all the character strings that are matches to the strings on Line #1. If none match, then print NONE. # is used here to represent the empty string.
SAMPLE
INPUT
#, aac, acc, abc, ac, abbc, abbbc, abbbbc, aabc, aabbc
a.c
a[ab]c
a[^ab]c
ab*c
a.b{2,4}c
OUTPUT
aac, acc, abc
aac, abc
acc
ac, abc, abbc, abbbc, abbbbc
aabbc, abbbc, abbbbc