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.
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 "*".
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".
6 BELLS TELLS FALLS DOLLS DULLS DOLLIES SELLS *ELLS D?LLS D?LL* *LL*
NO MATCH BELLS, TELLS DOLLS, DULLS DOLLS, DULLS, DOLLIES BELLS, TELLS, FALLS, DOLLS, DULLS, DOLLIES
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008
C++03, PAS, C, HASK, ASM, TEXT, CAML, C#, C++11
~a question mark is next to a star
~there are more than 2 stars / a star can be in the middle of the test case