Kompresija

Osnovne informacije

Omejitve
  • Čas: 5 s
  • Spomin: 256 MB
Avtor:
  • UPM

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Programi za kompresijo podatkov sodijo med najbolj uporabne "algoritmične" programe. Še posebej pomembni so postali z razvojem prenosa podatkov po žici, najprej preko direktnih modemskih povezav, kasneje pa po internetu. Kljub temu, da so internetne povezave v zadnjem času dosegle že zelo velike pasovne širine, kompresija še vedno močno pospeši prenos datotek po medmrežju. Zato še vedno nastajajo novi tovrstni programi z vedno večjo stopnjo kompresije (pravzaprav to ni čisto res - že dolgo so znani algoritmi, ki se približajo teoretični meji stisljivosti podatkov, vendar so večinoma prepočasni za uporabo).

Kompresijski algoritem, ki ga bomo predstavili v tej nalogi se ne more pohvaliti, da dosega teoretično mejo kompresibilnosti. Vsekakor pa se s pravkar omenjenimi algoritmi ujema v tem, da je prepočasen za uporabo.

Za razliko od večine sodobnih algoritmov, ki uporabljajo metodo drsečih slovarjev in Huffmanovo ali aritmetično kodiranje, naš algoritem temelji na enostavni ugotovitvi, da se včasih kak podniz v celotnem nizu pojavi večkrat zaporedoma. Takrat lahko niz krajše predstavimo tako, da ponavljajoči se podniz navedemo le enkrat, v oklepajih, predenj pa postavimo število pojavitev. Enak postopek lahko uporabimo tudi za predstavitev samega podniza (če se v njem ponavlja kakšen še krajši podpodniz). Na primer, niz ABCDEDEDECDEDEDEA lahko krajše zapišemo kot AB2(CDEDEDE)A, še krajše pa kot AB2(C3(DE))A. Še en primer: niz WVWVWVVVVVVVVVV lahko zapišemo kot W2(VW)10(V), lahko pa tudi kot 3(WV)9(V).

Seveda bi radi z našim algoritmom sodelovali na tekmovanju najboljših kompresijskih metod. Da pa se tam ne bi osmešili, bomo raje najprej preizkusili učinkovitost algoritma. Zato potrebujemo program, ki bo za dani vhodni niz ugotovil, kako dolga je najkrajša v prejšnjem odstavku opisana predstavitev.

Vhodni podatki

V prvi vrstici je število testnih primerov (celo število, vsaj 1 in največ 10). Sledijo testni primeri, vsak je v svoji vrstici. Vrstica za posamezni testni primer vsebuje le niz, ki ga moraš komprimirati; dolg je vsaj 1 in največ 100 znakov, vsi znaki pa so velike črke angleške abecede.

Izhodni podatki

Izpiši po eno vrstico za vsak testni primer. Vanjo izpiši dolžino najkrajšega niza, s katerim se da po pravilih iz besedila naloge predstaviti dani vhodni niz pri tistem testnem primeru.

Primer

Vhod

5
ABCDEDEDECDEDEDEA
WVWVWVVVVVVVVVV
ABCDE
BCDDCDDCDD
UUVUUVUWUWWUWUUVUUVUWUWWUW

Izhod

12
9
5
7
16
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task