Contando patrones#2604

Contando patrones

1 segundo
128 megabytes

Dada una cadena y un conjunto de patrones, determine para cada patrón la cantidad de posiciones en las que aparece en la cadena.

Entrada

La primera línea contiene una cadena de longitud n~(1 \le n \le 10^5).

La segunda línea contiene un entero k~(1 \le k \le 5 \cdot 10^5) — la cantidad de patrones. Cada una de las siguientes líneas contiene un patrón. La longitud total de todos los patrones no supera 5 \cdot 10^5.

La cadena y los patrones consisten en letras minúsculas del alfabeto latino '' - ''.

Salida

Para cada patrón, imprima en una línea separada la cantidad de sus apariciones en la cadena.

Ejemplos

Ejemplo 1

Loading
Loading