Matcom Online Grader

Fito está jugando con sus amigos un juego llamado “La cinta mágica”. Este juego consiste en una cinta de papel que tiene escrito una secuencia de letras mayúsculas. Estas letras no tienen que formar palabras ni tener ningún sentido. En cada turno un jugador debe formar varias palabras usando la cinta. Cada palabra formada vale un punto y gana el jugador que mayor puntuación tenga. Lo jugadores pueden formar las palabras en cualquier orden y no pierden puntos por no formar alguna. Para formar una palabra el jugador puede buscarla en la cinta como una subcadena. Otra opción es dividir la palabra en dos partes y buscar cada una en la cinta. Si encuentra ambas partes entonces haciendo un doblez en la cinta puede formar la palabra. Hay que tener en cuenta que el doblez es equivalente a eliminar las letras entre una parte y otra, por lo que el orden entre ellas debe ser igual al que tenían en la palabra y no puede haber solapamientos.

Las palabras son escogidas por todos los jugadores antes de empezar el juego y se escriben en las cartas que el jugador de turno escoge aleatoriamente. Cuando los jugadores están inventando las palabras no pueden ver la cinta, para evitar así trampas. Esto ocasiona que algunas de las palabras inventadas sean imposible de formar usando la cinta. Para evitar que el juego termine con muy pocos puntos hay una aplicación que nos dice para un conjunto de palabras cuantas pueden ser formadas con la cinta. Desgraciadamente Fito no tiene dicha aplicación. Como estudiante de computación él cree que no debe ser tan difícil de hacer y ha empezado a programarla. Ahora solo queda hacer el método principal que cuenta la cantidad de palabras que pueden ser formadas con la cinta. Hay que tener en cuenta que este método debe ser rápido para que los jugadores no se aburran esperando por su respuesta.

La primera línea de la entrada es una cadena $S (2 \leq |S| \leq 100000)$ con las letras que aparecen en la cinta. Le sigue un entero $m (2 \leq m \leq 100)$ la cantidad de palabras que se van a usar en el juego. Las siguientes $m$ líneas contienen las palabras de este juego. Todas las palabras son distintas y  $2 \leq |W_i | \leq 1000$.

La salida es un entero con la cantidad de palabras que pueden ser encontradas en la cinta siguiendo las reglas del juego.