WC '95 P4 - Wildcard

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem type
Woburn Challenge 1995

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 match 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 (e.g. PRIME.PAS, PRINTER.PAS). The pattern *TST matches all strings containing the substring TST (e.g. TSTING.PAS, PRIME.TST, ATSTART.EXE, TST). The pattern PSY???? matches all seven-letter words with the prefix PSY (PSYCHIC, PSYCHED, PSYCHOS).

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

Input Specification

The first line will contain a number N in the range 1 \dots 1\,000, 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 uppercase letters AZ 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 uppercase letters, periods, and the wildcards ? and *.

Output Specification

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

Comments

There are no comments at the moment.