Pattern Matching

Time limit1sMemory limit128 MB

Summary
Decide whether digit sequences match patterns where digits match exactly and * and # stand for even and odd counts of arbitrary digits.
Level

Hard8 of 10

Topics
Dynamic programming, String matching
Solved
No attempts yet

Problem

In computer science, pattern matching is the act of checking whether a sequence conforms to (matches) a given pattern. In this problem we express patterns over sequences of decimal digits using a small set of rules.

A pattern is a string of length at least one made up of decimal digits 0–9, asterisks *, and hash signs #.

  • A digit matches exactly itself.
  • * denotes an even number (0, 2, 4, …) of arbitrary digits.
  • # denotes an odd number (1, 3, 5, …) of arbitrary digits.

For example, the pattern 129 matches only the sequence 129. The pattern 1*3 matches every sequence that begins with 1, ends with 3, and has an even number of digits between the first and last digit. As another example, the pattern #55 matches 155, 12355, and 1234555, but none of 55, 1255, or 123455.

Write a program that decides whether a given sequence matches a given pattern.

Input

The input consists of one or more data sets. Each data set contains a single pattern and one or more sequences to match against it.

The first line of each data set is the pattern; each following line is a sequence to compare against that pattern. The end of every data set except the last is marked by the word END on its own line, and the end of the last data set is marked by the word QUIT on its own line.

Every line is at most 100,000 characters long.

Output

For each sequence, print one line in the following format:

k.s. result

where k is the data set number (starting at 1), s is the sequence number within that data set (restarting at 1 for each data set), and result is match if the sequence matches the pattern and not otherwise.

Examples2

  1. Example 1

    Input
    129
1299
129
1129
END
1*3
123
1223
END
#55
155
12355
55
1255
QUIT
    Expected output
    1.1. not
1.2. match
1.3. not
2.1. not
2.2. match
3.1. match
3.2. match
3.3. not
3.4. not

  2. Example 2

    Input
    *
12
123
1234
END
#
1
12
123
QUIT
    Expected output
    1.1. match
1.2. not
1.3. match
2.1. match
2.2. not
2.3. match