Woburn Challenge 1995

Problem 4: Wildcard

Wouldn't it be nice to list all of your files that end with the suffix ".PAS", or only those containing the string "TST"? Wouldn't it be nice to retrieve all seven-letter words beginning with "PSY" from an electronic dictionary?

If you haven't guessed by now, you must write a program that will math strings in a list to various patterns. To make the problem interesting, patterns can have the following wildcards:

"?" - matches any single character
"*" - matches any series of 0 or more characters

For example, the pattern "*.PAS" matches all strings ending with the suffix ".PAS" (eg PRIME.PAS, PRINTER.PAS). The pattern "*TST*" matches all strings containing the substring "TST" (eg TSTING.PAS, PRIME.TST, ATSTART.EXE, TST). The pattern "PSY????" matches all seven-letter words with the prfix "PSY" (PSYCHIC, PSYCHED, PSYCHOS).

Write a program that can look for matches to a given pattern which can contain any number of wildcards.

Input

The first line contains a number N in the range 1..1000, the number of words in your "matching dictionary".
The next N lines each contain a unique word for your dictionary. These words will contain only the upper-case letters "A".."Z" and periods and be 20 characters or less.
The next 5 lines each contain a pattern which your program should find the matches for. These strings will contain only upper case letters, periods, and the wildcards "?" and "*".

Output

For each of the 5 search patterns, output a comma-separated list of all the matches found in the dictionary. The results should appear in the same order as given in the dictionary. If no match is found output "NO MATCH".

Sample Input

6
BELLS
TELLS
FALLS
DOLLS
DULLS
DOLLIES
SELLS
*ELLS
D?LLS
D?LL*
*LL*

Sample Output

NO MATCH
BELLS, TELLS
DOLLS, DULLS
DOLLS, DULLS, DOLLIES
BELLS, TELLS, FALLS, DOLLS, DULLS, DOLLIES

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, TEXT, CAML, C#, C++11

Comments (Search)

is it possible to have test cases where:

~a question mark is next to a star
(eg. *??L?S?*)

~there are more than 2 stars / a star can be in the middle of the test case
(eg.*DO*EI*)

???

Whyever not?

(Read: yes.)