SPOJ.com - Problem FR_18

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_18_19 - Magiczny mur

W Bajtocji istniał magiczny mur, na którym mieszkańcy zapisywali swoje imiona, tworząc jednolity i kolorowy wzór. Jednego dnia, pewien mały chłopiec o imieniu Filip postanowił dołączyć swoje imię do tego bardzo długiego ciągu. Podczas gdy malował litery na magicznym murze, inny mieszkaniec, Kamil, obserwował go z uśmiechem na twarzy.

Następnego dnia zaintrygowani mieszkańcy zaczęli badać, ile razy konkretne imię pojawiło się na murze. Okazało się, że imię Filip było jednym z najczęstszych. Ludzie zaczęli rozważać, czy to ze względu na popularność imienia czy też może przez magię związaną z Filipem, właśnie to imię było zapisywane najczęściej.

Zadanie polega na policzeniu, ile razy dane imię występuje na magicznym murze Bajtocji, abyśmy mogli lepiej zrozumieć, jakie tajemnice kryją się za tym urokliwym miejscem.

Wejście

W pierwszym miejscu ciąg dużych liter reprezentujących imiona zapisywane przez mieszkańców Bajtocji (nie dłuższy niż milion znaków).

W drugim wierszu jedna liczba q definiująca ilość zapytań (nie więcej niż milion).

Wyjście

Dla każdego zapytania jedna liczba określająca ilość wystąpień danego imienia.

Przykład 1

Wejście:

ADAMFILIPADAMADAMFILIPKAMILFILIPFILIP
2
FILIP
KAMIL

Wyjście:

4
1

Przykład 2