패턴 매칭
시간 제한1초메모리 제한128 MB
숫자는 그대로 일치하고 *와 #는 임의의 짝수 및 홀수 개수의 숫자를 뜻하는 패턴에 대해 각 문자열이 일치하는지 판정한다.
문제
컴퓨터 과학에서 패턴 매칭은 어떤 수열이 주어진 패턴에 부합(일치)하는지 확인하는 작업입니다. 이 문제에서는 십진 숫자로 이루어진 수열에 대한 패턴을 간단한 규칙으로 표현합니다.
패턴은 십진 숫자 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 입니다.