1999-2000 ACM North Central Regional Programming Contest

Problem 3 — Wild Cards

The ability to use wild card characters to select file names is common in many operating system command languages. The mechanism used is as follows:

1. A set of file names S is given from which file names will be selected. This is frequently the set of names of files in the current directory.
2. A pattern P is given that may include zero or more wild card characters.
3. The pattern P is tested against each file name in S, with those that match the pattern being selected.

Patterns can be formed in different ways depending on the command language. In MS-DOS, for example, the wild card character ‘?’ will match any single character, and the wild card character ‘*’ will match any sequence of adjacent characters of length 0 or more. Any other non-blank character will only match itself. For example, the pattern A?*?X will match file names ABCX, ABCDX, and ABCDEX, but will not match AX or ABX. The pattern *X* will match any file name that includes an X anywhere, while the pattern ?X* will match any file name with at least two characters that has an X in the second position. Note that the pattern X**X will match what X*X matches.

In this problem you are to determine which file names in a given set match each of a sequence of patterns that may include the * and ? wild card characters. These wild card characters are to be interpreted as described in the preceding paragraph.

Input

The input will begin with a set of file names, one per line starting in the first column and ending with the end of line. File names will include only upper and lower case alphabetic characters and decimal digits. The case of the alphabetic characters is significant (that is, ‘A’ is not the same as ‘a’). A line containing a single dollar sign (‘$’) follows the last line of the set of file names.

Following the file names will appear a sequence of patterns, one per line starting in the first column and ending with the end of line. Patterns will include only upper and lower case alphabetic characters, digits, asterisks (‘*’) and question marks (‘?’). A line containing a single dollar sign (‘$’) indicates the end of the sequence of patterns.

Each pattern and filename will contain between 1 and 20 characters.

Output

For each pattern, determine which file names in the set are matched. Display the pattern and the matching file names in a format similar to that shown the sample output below. Note that the matching file names are to be displayed in the order they appeared in the input.

Sample Input

AX

ABX

ABCX

ABCDX

ABCDEX

ABCDEF

AABBCC

XXXXYXXXXX

$

ABCDEF

ABCDE

A?*?X

*X*

?X*

X*X

X**X

A?C*

A*

AA*

*X*Y*X*

$

Expected Output

Case 1. Pattern ABCDEF matches...

ABCDEF

Case 2. Pattern ABCDE matches...

Case 3. Pattern A?*?X matches...

ABCX

ABCDX

ABCDEX

Case 4. Pattern *X* matches...

AX

ABX

ABCX

ABCDX

ABCDEX

XXXXYXXXXX

Case 5. Pattern ?X* matches...

AX

XXXXYXXXXX

Case 6. Pattern X*X matches...

XXXXYXXXXX

Case 7. Pattern X**X matches...

XXXXYXXXXX

Case 8. Pattern A?C* matches...

ABCX

ABCDX

ABCDEX

ABCDEF

Case 9. Pattern A* matches...

AX

ABX

ABCX

ABCDX

ABCDEX

ABCDEF

AABBCC

Case 10. Pattern AA* matches...

AABBCC

Case 11. Pattern *X*Y*X* matches...

XXXXYXXXXX