패턴 매칭
면접 대비시간 제한20초메모리 제한1024 MB
와일드카드 * 패턴 N개를 모두 만족하는 길이 10^4 이하의 이름을 하나 찾고, 없으면 *를 출력합니다.
문제
많은 터미널은 별표(*)를 빈 문자열을 포함한 임의의 문자열을 뜻하는 기호로 쓴다. 예를 들어 BASH*에 맞는 파일을 나열하면 BASH, BASHER, BASHFUL이 나올 수 있다. *FUL에서는 BEAUTIFUL, AWFUL, BASHFUL이, B*L에서는 BASHFUL, BEAUTIFUL, BULL이 나올 수 있다.
패턴은 대문자 영어 알파벳과 별표로만 이루어진 문자열이다. 이름은 대문자 영어 알파벳으로만 이루어진 문자열이다. 패턴 p의 별표를 각각 빈 문자열일 수도 있는 임의의 문자열로 바꿔서 이름 m을 만들 수 있으면 p는 m과 일치한다. 별표마다 서로 다른 문자열로 바꿔도 된다.
N개의 패턴이 주어졌을 때, 모든 패턴과 동시에 일치하는 이름을 10^4 글자 이하로 하나 찾아라. 그런 이름이 없으면 그 사실을 보고하라.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 패턴의 수 N이 적힌 줄로 시작한다. 이어서 N개의 줄에 패턴 Pi가 한 줄에 하나씩 주어진다. 같은 패턴이 여러 번 나올 수 있다.
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. y는 모든 Pi와 일치하는 10^4 글자 이하의 이름 중 아무거나 하나다. 그런 이름이 없으면 *를 출력한다.
제한
1 <= T <= 100
2 <= N <= 50
2 <= Pi의 길이 <= 100
Pi의 각 문자는 대문자 영어 알파벳 또는 별표다.
각 Pi에는 대문자 영어 알파벳이 최소 하나 있다.
힌트
예제 1에서 다른 정답으로는 COCOCONUTS와 ILIKECOCONUTS가 있다. COCONUTSAREGREAT와 COCOANUTS는 정답이 될 수 없다.
예제 2에서는 조건을 만족하는 이름이 없으므로 정답은 *다.
패턴 H*O, HELLO*, *HELLO, HE*는 HELLO 또는 HELLOGOODBYEHELLO로 맞출 수 있다. OTHELLO와 HELLOO는 정답이 될 수 없다.
패턴 CO*DE와 J*AM에는 공통으로 맞는 이름이 없으므로 정답은 *다.
패턴 CODE*와 *JAM은 CODEJAM으로 맞출 수 있다.
패턴 A*C*E와 *B*D*는 ABCDE 또는 ABUNDANCE로 맞출 수 있지만, BOLDFACE는 정답이 될 수 없다.
패턴 A*C*E와 *B*D에는 공통으로 맞는 이름이 없으므로 정답은 *다.
패턴 **Q**와 *A*는 QUAIL 또는 AQ로 맞출 수 있다.