Državno natjecanje iz informatike 2016. / Druga podskupina (3. i 4. razred) – Prvi dan natjecanja - 1. zadatak

Trigrami su trojke znakova pomoću kojih se na jednostavan način može definirati sličnost riječi te se često koriste prilikom pretraživanja teksta.

U ovom zadatku proširujemo osnovnu ideju na pretraživanje fraza.

Neka je riječ niz od jednog ili više malih slova engleske abecede, a fraza niz od jedne ili više riječi odvojenih s po jednim razmakom.

Skup trigrama fraze w označavamo s T(w) te ga dobijemo tako da ispred i iza w dodamo znak “#”, zamijenimo svaki razmak u w također znakom “#” te, konačno, uzmemo svaki niz od točno tri susjedna znaka ignorirajući pritom trigrame koje smo već dodali.

Tako je, na primjer, skup trigrama za frazu “rat i mir” jednak {#ra, rat, at#, t#i, #i#, i#m, #mi, mir, ir#}.

Neka |X| označava broj elemenata skupa X. Sličnost dvije fraze w i v definiramo kao kvocijent broja zajedničkih trigrama te ukupnog broja trigrama koji su sadržani u barem jednoj od fraza:

Zadana je fraza w te tekst t (također niz riječi odvojenih razmakom).

Odredite frazu v koja se pojavljuje u tekstu t kao niz uzastopnih riječi te je, od svih takvih, najsličnija frazi w.

Ukoliko postoji više najsličnijih fraza ispišite onu koja se sastoji od najmanjeg broja riječi, a ako još uvijek postoji više najsličnijih, ispišite onu koja se pojavljuje najranije u tekstu t.

Ulazni podaci

U prvom redu nalazi se prirodni broj n (n ≤ 50) – broj riječi u frazi w. U sljedećem redu nalazi se fraza w – niz od n riječi odvojenih s po jednim razmakom.

U sljedećem redu nalazi se prirodni broj m (m ≤ 500) – broj riječi u tekstu t.

U sljedećem redu nalazi se tekst t – niz od m riječi odvojenih s po jednim razmakom.

Svaka riječ u frazi w i u tekstu t je niz od najviše 10 malih slova engleske abecede.

Izlazni podaci

U prvi red ispišite niz riječi odvojenih s točno jednim razmakom – traženu frazu.

Primjer zadatka

Ulaz

1
abc
3
def ghi jkl

Izlaz

def

Ulaz

2
hotel zora
6
rana zora motel zora hostel zora

Izlaz

motel zora

Objašnjenje

Pojašnjenje drugog primjera: U sljedećoj tablici se nalaze sve fraze sadržane u tekstu te sličnost svake sa zadanom frazom.