Problem 6: Shell Regular Expressions

Background:

UN*X shells, such as bash, sh, ksh, etc, use modified regular expressions (regexp) to match filenames. This is useful, to say, remove a whole bunch of annoying files at once (such as, rm -f *.dll). In this problem, you get to match a variations of shell regexps to filenames.

For our purposes, a regexp is:

  1. character -- matches itself exactly
  2. * -- matches 0 or more characters
  3. ? -- matches exactly one character
  4. + -- matches 1 or more characters (equivalent to ?*)
  5. ~ -- matches 0 or 1 character
In real regexp, the modifiers above would apply to the previous regexp. In UN*X shells, and this problem, the modifiers apply to characters coming up. A character is any printable ASCII character. Matches are case sensitive, so A does not match to a.

For example, the expression a*b* matches the filenames ab, aaabbbbbb, acbe, abe, and so on. a~b would match ab, acb, aAb, etc, but not aaab.

Input:

Each test case consists of a series of lines. The first line has the format N regexp, where N is a positive integer, and regexp is a regular expression, no more than 60 characters long. There will be at least one space separating the two.

Following the first line will be N filenames to be matched against regexp. A filename may consist of any printable character, except those used for the regular expressions.

No spaces will apear in the filenames or in the regexp.

No line of input will exceed 80 characters.

Output:

Print out each filename that matches the given regular expression. At the end of each test case, print the message
There were # matching filenames.
where # is the number of filenames that matched the regular expression. Do not conjugate any word in the sentence to match #, ie, if there was one matching item, then print There were 1 matching filenames.

Sample Input:

4 a*bc
abc
aaabcbcbcbcbcbcaaabc
abbcb
aAAAABC
3 a?tyoz~bbbb??23
abtyozbbbbbb23
atyozbbbbbb23
ab

Sample Output:

abc
aaabcbcbcbcbcbcaaabc
There were 2 matching filenames.
abtyozbbbbbb23
There were 1 matching filenames.