Srednješolsko tekmovanje ACM iz računalništva in informatike

Najkrajši skupni nadniz

Podroben opis naloge

Danih je več nizov, ki jih sestavljajo male črke angleške abecede. Naloga je poiskati kakšen čim krajši niz, v katerem se kot podnizi pojavljajo vsi dani vhodni nizi. Z drugimi besedami torej iščemo čim krajši skupni nadniz vseh vhodnih nizov. Pri tem so dovoljene tudi take pojavitve podnizov, v katerih se črke podniza ne pojavljajo strnjeno skupaj (na primer: niz aaa je podniz niza ananas).

Primer: recimo, da imamo vhodne nize miza, zima in mazivo. Nekaj primernih nizov, ki so skupni nadnizi vseh treh vhodnih nizov, je na primer:

abcdefghijklmizazivonopqrstuvwxyzima (36 znakov)
mizazimamazivo (14 znakov)
mizimazivo (10 znakov)
miazimavo (9 znakov)
mazizmavo (9 znakov)

Izkaže se, da je 9 znakov pri tem konkretnem primeru najboljša možna rešitev — noben skupni nadniz vseh treh vhodnih nizov ni krajši od 9 znakov.

Ocenjevalni program

Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk17Nadniz.cpp.

Na voljo je tudi prevedena različica ocenjevalnega programa (za Windows).

Oblika vhodne datoteke

Pri tej nalogi so vsi testni primeri podani v eni vhodni datoteki. V prvi vrstici vhodne datoteke je niz z imenom naloge (Nadniz), v drugi pa število testnih primerov (T). Sledijo testni primeri, pred vsakim od njih pa je še ena prazna vrstica.

Posamezni testni primer se začne z vrstico, ki vsebuje dve celi števili, ločeni z enim presledkom: najprej številka testnega primera (od 1 do T), nato pa n, ki pove število vhodnih nizov pri tem testnem primeru. Sledi še n vrstic, v vsaki od njih pa je po eden od vhodnih nizov. Vhodni nizi so sestavljeni le iz malih črk angleške abecede (od a do z), dolžina posameznega vhodnega niza je vsaj 1 znak, skupna dolžina vseh vhodnih nizov pri posameznem testnem primeru pa je kvečjemu 1000000 znakov.

Primer: če bi imeli en sam testni primer, in sicer tistega z začetka naloge, bi bila vhodna datoteka takšna:

Nadniz
1

1 3
miza
zima
mazivo

V resnici bo pri tej nalogi 60 testnih primerov; za ilustracijo je tule prvih nekaj vrstic prave vhodne datoteke:

Nadniz
60

1 100
dccadaabd
ccccee
acbbdaccaceaeabcec
...

Oblika izhodne datoteke

Oddaš lahko poljubno število izhodnih datotek s svojimi rešitvami. Pri tem vsaka izhodna datoteka vsebuje rešitve za enega ali več testnih primerov. Če za isti testni primer oddaš več rešitev, bomo pri ocenjevanju upoštevali najboljšo med njimi.

Oblika posamezne izhodne datoteke je naslednja:

V prvi vrstici naj bo koda, ki si jo dobil(a) ob registraciji in iz katere je razvidno, da si rešitev res poslal(a) ti, ne pa kdo drug. V drugi vrstici naj bo ime naloge (Nadniz). Sledijo naj tvoje rešitve za enega ali več testnih primerov.

Vsaka rešitev se začne s prazno vrstico. V drugi vrstici naj bo številka testnega primera, na katerega se nanaša ta rešitev. Sledi naj še vrstica, ki vsebuje nek (čim krajši) skupni nadniz vseh vhodnih nizov pri tem testnem primeru. Ta nadniz sme vsebovati le male črke angleške abecede in sme biti dolg največ toliko, kolikor so dolgi vsi vhodni nizi tega testnega primera skupaj.

Primer: če bi bila naša uporabniška koda enaka 123456 in bi obstajal prvi testni primer, kakršen je prikazan na vrhu te strani, bi lahko oddali spodnjo izhodno datoteko.

123456
Nadniz

1
mizimazivo

To ustreza tretji rešitvi iz zgornjih primerov; najdeni nadniz je veljaven, ni pa najkrajši možni (dolg je 10 znakov, obstajajo pa tudi taki z 9 znaki).

Vhodni podatki

nadniz.in — datoteka z vsemi vhodnimi podatki za to nalogo (9 MB).

Registracija

Preden lahko oddajaš svoje rešitve, se prijavi prek spodnjega obrazca. Dodelili ti bomo enolično uporabniško kodo, ki jo boš potreboval(a) za pripravo svojih izhodnih datotek.

Opomba: pri tej nalogi lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh tekmovalcev, za morebitne praktične nagrade pa pridejo v poštev le srednješolci/ke in študentje/ke.