DRŽAVNO NATJECANJE 2013. – Drugi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Mirko i Slavko igraju igru koja se sastoji od toga da u svakom koraku Mirko na papir napiše dva niza znakova T i P sastavljena od malih slova engleske abecede.

Niz P je manje duljine od niza T te vrijedi da T ne sadrži (kao podniz uzastopnih znakova) ni P niti niz koji dobivamo tako da obrnemo niz P (na primjer, ako je niz P 'abcd', tada T ne sadrži niz 'abcd' niti niz 'dcba').

Cilj igre je prebrojati određene okvire niza T.

Okvir niza T je niz uzastopnih pozicija u nizu T duljine jednake ili veće od duljine niza P.

Na primjer, ako je T jednak 'abab', a niz P jednak 'bb' onda T ima ukupno šest okvira: tri okvira duljine 2, dva okvira duljine 3, te jedan okvir duljine 4 (cijeli niz T).

Dva okvira su različita čak i ako su nizovi znakova koji se nalaze unutar njih jednaki.

Budući da se Mirko i Slavko ne mogu dogovoriti čije je rješenje točno zamolili su tebe da im napišeš program koji će za Q zadanih koraka za zadane nizove T i P pronaći broj okvira niza T takvih da vrijedi ako se obrne sadržaj tog okvira (prvi element okvira se zamjeni sa zadnjim, drugi sa predzadnjim, itd.) niz T sadrži niz P kao niz uzastopnih znakova.

Ulazni podaci

U prvom retku nalazi se Q (1 ≤ Q ≤ 15), broj koraka.

U sljedećih 2 * Q redaka ulaza nalaze se podaci o Q koraka igre.

Za svaki korak zadana su dva niza, svaki u svom retku, najprije niz T koji se sastoji od najmanje 3 i najviše 5000 malih slova engleske abecede, a zatim niz P koji se sastoji od malih slova engleske abecede te je kraće duljine od T.

Pri tome vrijedi da T ne sadrži (kao podniz uzastopnih znakova) ni P niti niz koji se dobije kada se niz P obrne.

Izlazni podaci

Potrebno je ispisati Q redaka – u svaki redak traženi broj okvira u odgovarajućem koraku igre.

Primjeri test podataka

Ulaz

1
abdccb
abc

Izlaz

2

Ulaz

1
aaamirokokokirimirimko
mirko

Izlaz

2