9 sep. 2009

Code Jam: 1er problema

Me he propuesto traducir los problemas de la competencia de programación mundial, organizada todos los años por Google (conocida como Google Code Jam).

Aunque he intentado que sea lo más próximo al planteamiento original en inglés, me he topado con algunos detalles, especialmente en lo que se refiere a nomenclatura informática que no he querido traducir para que no pierda el sentido original (input, output, dataset, etc).


"Lenguaje Alienígena"
Problema

Despues de años de estudio, científicos de los Laboratorios Google han descubierto un lenguaje alienígena, transmitido desde un planeta muy lejano. Ese lenguaje es especial porque cada palabra esta formada exactamente por L letras minúsculas. Por otra parte, existen exactamente D palabras.

Una vez que se construyó el diccionario de todas las palabras en tal lenguage, el siguiente hallazgo fue que los alienígenas habían transmitido mensajes a la Tierra en décadas pasadas.
Desafortunadamente, estas señales estaban dañadas, debido a la distancia entre nuestros planetas, y algunas de las palabras fueron malinterpretadas. Para ayudarlos a decifrar esos mensajes, los científicos te han pedido que idees un algoritmo para determinar la cantidad de posibles interpretaciones para un patrón dado.

Un patrón consiste exactamente en L "tokens". Cada token puede ser una letra minúscula (los científicos están seguros que este es un símbolo correcto) o un grupo de letras minúsculas sin repetirse, encerradas en paréntesis redondos ( y ). Por ejemplo: (ab)d(dc) quiere decir que la primera letra es 'a' o 'b', la segunda es definitivamente una 'd' la tercera una 'd' o una 'c'.
Dicho de otro modo, el patrón (ab)d(dc) puede ser una de estas 4 posibilidades: add, adc, bdd, bdc.

Input

La primera línea de cada input contiene 3 enteros L, D y N, separados por un espacio.
Las D líneas siguientes contienen una palabra de longitud L (una palabra por línea).
Esa es la lista de palabras conocidas del lenguaje alienígena.
Los N casos de pruebas vienen a continuación, uno por línea, y consisten en un patrón tal como se describía anteriormente.
Se puede asumir que todas las palabras conocidas son únicas.

Output

Para cada caso de prueba, el output es

Case #X: K
Donde X es el número de caso de prueba, comenzando en 1, y K indica cuántas palabras en el lenguaje alienígena podrían coincidir con el patrón.


Límites

Dataset pequeño

1 = L = 10
1 = D = 25
1 = N = 10

Dataset grande

1 = L = 15
1 = D = 5000
1 = N = 500


Ejemplo



Input

Output

3 5 4



abc



bca



dac



dbc



cba



(ab)(bc)(ca)

Case #1: 2

abc

Case #2: 1

(abc)(abc)(abc)

Case #3: 3

(zyx)bc

Case #4: 0