Županijsko natjecanje 2014. / Osnovna škola (8. razred) - 3. zadatak

Marko i Ivan dosjetili su se nove igre za koju su potrebni samo papir, olovka i dobra volja.

Na početku igre Marko i Ivan međusobno se udalje i svatko na svoj papir nešto zapiše.

Marko na svoj papir zapiše niz uvjeta. Postoje četiri tipa uvjeta.

U tablici nam X označava malo slovo engleske abecede (a-z), a A i B nizove znamenaka (0-9) koji predstavljaju broj veći od nule.

Ivan za to vrijeme na svoj papir zapiše N riječi.

Riječ je niz malih slova engleske abecede.

Npr. niz Markovih uvjeta: “c{1,2}a{2,}b{3}” čitamo kao tekst: “Ivan će sada zaredom napisati barem 1, a najviše 2 slova c.

Ivan će sada zaredom napisati barem 2 slova a. Ivan će sada zaredom napisati 3 slova b.”

Tom nizu uvjeta odgovarale bi npr. riječi “caabbb” i “ccaaabbb”, dok riječi “cccaabbb”, “bbbaac”, “caabb” i još mnoge druge ne bi odgovarale.

Primjeri nekih Markovih nizova uvjeta i riječi koje odgovaraju tim uvjetima dani su u sljedećoj tablici.

Kada se prijatelji ponovno sastanu, moraju odrediti koje Ivanove riječi odgovaraju Markovim uvjetima.

Budući da to nije lagan posao, zamolili su tebe za pomoć.

Zadan je niz Markovih uvjeta.

Za svaku od Ivanovih N riječi ispiši “DA” ako odgovara uvjetima, a “NE” u suprotnom.

ULAZNI PODATCI

U prvom retku nalazi se string S koji predstavlja niz Markovih uvjeta opisan u tekstu zadatka.

U drugom retku nalazi se prirodan broj N (1 ≤ N ≤ 10), broj Ivanovih riječi.

U svakom od sljedećih N redaka nalazi se po jedan string koji predstavlja Ivanovu riječ.

Svaki string u ulaznim podacima imat će najviše 100 znakova.

IZLAZNI PODATCI

Za svaku od Ivanovih N riječi, u odgovarajući redak ispiši “DA” ako odgovara Markovim uvjetima, a “NE” u suprotnom.

PRIMJERI TEST PODATAKA

Ulaz

bac
3
ba
bacd
bac

Izlaz

NE
NE
DA

Ulaz

a{1,2}b{1,}c{2}d
5
abcd
abccd
aabbbccd
abcc
aaccd

Izlaz

NE
DA
DA
NE
NE

Ulaz

a{1,2}a{1}aa{2}
5
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa

Izlaz

NE
NE
DA
DA
NE