Fórum studentů MFF UK

Vstup:
neomezene velky soubor, jen 1. radek obsahuje max. 255 znaku.

Proces:
Hledat vsechny vybrane podposloupnosti ve tvaru 1. radku.

Vystup:
Pocet vsech vybranych podposloupnosti.

Priklad:
v souboru je na prvni radce slovo "SOS". Pak vysledek pro tento text: "ASOGSOSF" je 4. Existuji tam prave 4 vybrane podposloupnosti tvorici "SOS".

Omezeni:
Pamet 1MB
HDD nemame k dispozici vubec, jen ten jeden soubor na vstupu.
Maximalni pocet moznych vybranych podposloupnosti se vejde to 64-bitoveho integeru.

HDD k dispozici je, bez obmedzenia velkosti.

Mohol by niekto napisat vzorove riesenie?

Ano. Ale doporucuji ti si to nejdrive sam rozmyslet, jde celkem o jednoduchou myslenku.

Udelas si pole cisel (v tomto pripade 64-bitovych integeru), ktere bude dlouha tolik, kolik je znaku na prvnim radku, tzn. max 255. Kazda bunka bude reprezentovat jeden znak na tom prvnim radku. Pak zacnes cist ten soubor znak po znaku. Pokud nacteny znak je v prvnim radku, tak prochazis pole od konce a do kazde bunky, ktera reprezentuje ten znak (kdyz se v tom prvnim radku vyskytuje vicekrat stejny znak), prictes cislo, ktere je hned pred nim (smerem od zacatku). Do cisla na prvni pozici v poli pricitas vzdy 1. Az cely soubor projdes, tak na posledni pozici v poli budes mit vysledek.

Takze pro ten text: ASOGSOSF
a hledana podposloupnost je: SOS
SOS
0 0 0
1 0 0
1 1 0
1 1 0
2 1 1
2 3 1
2 3 4
2 3 4
takze text obsahuje 4x SOS.

Isiel som na to spredu a znova trebalo ist odzadu.... ach jo... Inac myslim si, ze jednoduchsie myslienky su tie najtazsie