DWITE '10 R3 #5 - E-Searching

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, December 2010, Problem 5

Searching 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:

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

For example, the search D??? matches all four letter words with 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 will contain 5 test cases. The first line of each test case contains an integer 1 \le N \le 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 will contain 5 lines per test case, 25 in total. Each line is a comma separated (with a space) list of all matches found in the dictionary. The results in the list appear in the same order as they do in the supplied dictionary. If no match is found output NO MATCH

Refer to the sample output for formatting.

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

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.