Problemas
정올 연구소는 미지의 세계와의 교신에 대한 연구를 진행하고 있는 연구소다. 어느 날 정올 연구소에서 외계어에 대한 신호를 잡아내었고, 이를 분석하게 되었다.
분석한 결과는 다음과 같다.
1. 외계어는 영문 소문자로 이뤄져있다. 2. 모든 외계어의 단어들의 길이는 동일하다.
저올 연구소는 외계어를 이루는 모든 단어를 입수하였다.
하지만, 그들의 대화 내용이 미약하게 잡혀 그들이 어떤 단어를 쓰는지를 명확하게 파악할 수는 없었다.
하지만, 찾아낸 대화의 내용에 대해 이것이 어떤 단어들로 해석 될 수 있는지를 알 수 있다면, 외계어에 대한 연구에 많은 도움이 될 것이다.
대화 내용의 예는 다음과 같다.
( abc ) cd ( bd )
여기서 괄호 안에 묶인 문자들은 해당 문자들 중 한 개의 단어로 해석될 수 있다는 것이며, 그렇지 않은 단어들은 그대로 해석됨을 뜻한다.
위의 예에서 나올 수 있는 단어들은 acdb, acdd, bcdb, bcdd, ccbd, ccdd가 있다.
이 중에서 외계어의 단어에 포함되는 단어를 찾는 것이 우리가 해야 할 일이다.
Entrada
입력의 첫번째 줄에는 외계어 단어들의 길이 L(1≤L≤15), 외계인 단어의 개수 D(1≤D≤5,000)
그리고 찾아낸 대화 내용 N(1≤N≤500)이 입력된다.
그 다음에 D개의 줄에 외계인의 단어들이 한 줄에 하나씩 주어지며, 단어들의 길이는 L로 고정되어 주어진다.
그 다음 N개의 줄에는 찾아낸 대화 내용이 입력된다.
대화 내용은 단어 하나로 이뤄져있다고 가정한다.
Salida
각 대화 내용에 대해서 이것이 몇 개의 외계어 단어로 해석될 수 있는지를 한 줄에 하나씩 출력한다.
Ejemplo
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc
2
1
3
0
Fuente
Google Code Jam 2009 Qualification Round A2번
Debes iniciar sesión para escribir código.