패턴 매칭

컴퓨터 과학에서 패턴 매칭은 어떤 수열이 주어진 패턴에 부합(일치)하는지 확인하는 작업입니다. 이 문제에서는 십진 숫자로 이루어진 수열에 대한 패턴을 간단한 규칙으로 표현합니다.

패턴은 십진 숫자 0–9, 별표 *, 우물 정자 # 로 이루어진 길이 1 이상의 문자열입니다.

• 숫자는 자기 자신과 정확히 일치합니다.
• * 는 짝수 개(0, 2, 4, …)의 임의의 숫자를 나타냅니다.
• # 는 홀수 개(1, 3, 5, …)의 임의의 숫자를 나타냅니다.

예를 들어 패턴 129 는 오직 수열 129 하고만 일치합니다. 패턴 1*3 은 1 로 시작하고 3 으로 끝나며, 첫 숫자와 마지막 숫자 사이에 짝수 개의 숫자가 있는 모든 수열과 일치합니다. 또 다른 예로 패턴 #55 는 155, 12355, 1234555 와는 일치하지만 55, 1255, 123455 와는 일치하지 않습니다.

주어진 수열이 주어진 패턴과 일치하는지 판정하는 프로그램을 작성하세요.

입력은 하나 이상의 데이터 집합으로 구성됩니다. 각 데이터 집합은 하나의 패턴과, 그 패턴에 대해 검사할 하나 이상의 수열로 이루어집니다.

각 데이터 집합의 첫 번째 줄에는 패턴이 주어지고, 이어지는 줄들에는 그 패턴과 비교할 수열이 한 줄에 하나씩 주어집니다. 마지막을 제외한 각 데이터 집합의 끝은 한 줄에 적힌 단어 END 로 표시되고, 마지막 데이터 집합의 끝은 한 줄에 적힌 단어 QUIT 로 표시됩니다.

모든 줄의 길이는 100,000자 이하입니다.

각 수열마다 한 줄에 다음 형식으로 출력하세요.

k.s. result

여기서 k 는 데이터 집합 번호(1부터 시작), s 는 해당 데이터 집합 안에서의 수열 번호(각 데이터 집합마다 1부터 다시 시작)이며, result 는 수열이 패턴과 일치하면 match, 일치하지 않으면 not 입니다.