DWITE Online Computer Programming Contest

E-Searching

December 2010
Problem 5

Looking up words in a dictionary can be painstaking. That’s why we’ve come up with an online dictionary that makes it really easy to search for words. To make life easier for the user, you can insert the following characters to broaden your search:

For example, the search D??? matches all four-letter words with the prefix “D” (e.g. DIRT, DUST, DUNK, etc...). Given a dictionary of words and a few search queries, give the list of words returned by each query.

The input file DATA5.txt will contain 5 test cases. The first line of each test case contains an integer 1 ≤ N ≤ 1000, the number of words in the dictionary. The next N lines each contain a unique word, consisting of only capital letters, up to 256 characters in length. The next 5 lines are test queries, consisting of capital letters, ?, and *.

The output file OUT5.txt will contain 5 lines per test case, 25 in total. Each line is a list of all matches found in the dictionary, where words are separated by comma and space. The results in the list appear in the same order as they do in the supplied dictionary. If no match is found, then output NO MATCH.

Refer to the sample output for formatting.

Sample Input (only first shown):
6
BELLS
TELLS
FALLS
DOLLS
DULLS
DOLLIES
SELLS
*ELLS
D?LLS
D?LL*
*LL*
Sample Output (only first shown):
NO MATCH
BELLS, TELLS
DOLLS, DULLS
DOLLS, DULLS, DOLLIES
BELLS, TELLS, FALLS, DOLLS, DULLS, DOLLIES