Školsko natjecanje iz informatike 2019. / Prva podskupina (3. i 4. razred) - 1. zadatak

Vjerojatno vam je poznato da svaka riječ u sebi sadrži manje riječi, takozvane podriječi. Tako npr. riječ INFORMATIKA kao podriječi sadrži npr. INFO, MAT, FORMAT, te mnoge druge podriječi. U zadanoj riječi možemo otkriti još više manjih riječi ako dopustimo „preskakanje“ nekih slova, tj. ako dopustimo da slova manje riječi ne budu nužno uzastopna u velikoj riječi. Na taj način u riječi INFORMATIKA možemo „pročitati“ npr. riječi IRMA ili FOTKA.

U ovom zadatku promatrat ćemo riječi koje možemo dobiti čitanjem nekih slova zadane riječi (s lijeva na desno) uz dopušteno preskakanje, ali tako da pročitana slova budu pravilno razmaknuta. Preciznije, kažemo da je riječ X pravilan podniz riječi Y ako je riječ X sadržana u riječi Y tako da se između slova riječi X nalazi uvijek jednak broj preskočenih slova riječi Y. Evo primjera:

• Riječ FRA pravilan je podniz riječi INFORMATIKA (između obilježenih slova F, R, A nalazi se po jedno preskočeno slovo). S druge strane, riječi IRMA i FOTKA nisu pravilni podnizovi riječi INFORMATIKA.

• Riječ META pravilan je podniz riječi MATEMATIKA (između obilježenih slova M, E, T, A nalaze se po dva preskočena slova).

• Naravno, možemo preskakati i nula slova, što znači da su obične podriječi (npr. FOR ili MAT u riječi INFORMATIKA) također pravilni podnizovi. To vrijedi i za jednoslovne podriječi, a tako je i svaka riječ pravilan podniz same sebe.

Napišite pogram koji unosi riječ i nekoliko „kandidata“ od kojih za svaki treba odgovoriti radi li se o pravilnom podnizu zadane riječi.

Ulazni podaci

U prvom retku nalazi se riječ \(Y\) sastavljena od \(N\) \((3 \leq N \leq 20)\) velikih slova engleske abecede. U sljedećem retku nalazi se prirodan broj \(K\) \((2 \leq K \leq 6)\), broj kandidata. U svakom od sljedećih \(K\) redaka nalazi se kandidat – riječ sastavljena od barem jednog, a najviše \(N\) velikih slova engleske abecede

Izlazni podaci

Za svaku od \(K\) riječi (kandidata) u zaseban redak velikim slovima ispišite \(DA\) ili \(NE\) ovisno o tome radi li se o pravilnom podnizu riječi \(Y\).

Primjeri test podataka

Ulaz

MATEMATIKA
6
MK
TATA
META
TEMA
MOTIKA
AEAIA

Izlaz

DA
NE
DA
DA
NE
DA