2. Reťazce v Lemingove vzorové riešenie

Podúloha a.

V prvej podúlohe si stačilo poriadne prečítať, ako sa lemingovia hýbu, a následne tento pohyb odsimulovať na zadanom slove BBABKAABABABKA. simuláciu. Odporúčame sa na to pozrieť.)* Celú simuláciu si môžete pozrieť na tomto obrázku:

Po prečítaní BBAB sú lemingovia usporiadaní takto:

a po prečítaní BBABKAABABABK nasledovne:

Otázka v tejto podúlohe okrem toho bola, koľkokrát sa v texte BBABKAABABABKA nachádza slovo BABKA a ako to súvisí s pohybom lemingov. Ľahko zistíme, že v tomto slove sa slovo BABKA nachádza na dvoch miestach. Keď si navyše odsimulujeme pohyb lemingov, všimneme si, že vždy keď toto slovo končí, jeden leming príde do cieľového domčeka. Ak sme totiž prečítali slovo BABKA postupne sa nad každou jamou objavil most. Leming, ktorý sa zo štartovacieho domčeka vynoril keď sme začali čítať túto časť textu, tak má vždy most, na ktorý vie stúpiť a postupne príde do konca. Táto vlastnosť platí aj naopak. Ak leming príde do cieľového domčeka, znamená to, že počas jeho cesty sa pred ním museli objavovať mosty a teda sme prečítali slovo BABKA. Vidíme, že počet slov tvorených písmenami z jám v zadanom texte je rovnaký ako počet lemingov, ktorým sa podarilo prísť do cieľa.

Podúloha b.

Našou úlohou je vymyslieť 15 písmenný text, ktorý obsahuje slovo KATKA čo najviac krát. Je jasné, že ak budeme toto slovo opakovať jedno za druhým, zopakujeme ho 3 krát a vytvoríme text KATKAKATKAKATKA.

Ide to však aj lepšie a k tomu nám pomôžu práve lemingovia. Je napríklad jasné, že hľadaný text bude začínať slovom KATKA..., toto je totiž najrýchlejší spôsob ako dosiahnuť prvú zhodu a z každého textu, ktorý by takto nezačínal by sme mohli prvé písmeno odstrániť bez toho aby sme zmenšili počet výskytov. Takisto už vieme, že počet výskytov slova KATKA v texte je totožný počtu lemingov, ktorí prešli ponad jamy s písmenami slova KATKA. Vytvorme si teda takéto jamy a prečítajme začiatok textu, teda KATKA.... Dostaneme nasledovnú situáciu.

Ako vieme dosiahnuť ďalší výskyt slova KATKA? Tak, že niektorého leminga dostaneme do cieľa. A najrýchlejšie to zvládne leming, ktorý stojí za druhou jamou. Aké písmená musíme prečítať aby prišiel do cieľa? Predsa tie, ktoré sú v jamách pred ním, teda T, K a A. Pridaním troch písmen dostaneme ďalší výskyt a náš text vyzerá: KATKATKA.... V tomto momente je však situácia úplne rovnaká ako na obrázku a najbližšie k cieľu je opäť leming stojaci za druhou jamou. Dostávame preto text KATKATKATKATKAT, v ktorom sa slovo KATKA nachádza štyrikrát.

Samozrejme, k tomuto riešeniu sa dalo prísť čisto pozorovaním a skúšaním, je však pekné sa pozrieť na to, ako toto riešenie vlastne súvisí s pohybom lemingov a čo nám vedia o riešení prezradiť.

Podúloha c.

V podúlohe c. nastala situácia, v ktorej sme sledovali ako sa jeden leming postupne dostal až k cieľovému domčeku. Bohužiaľ sme si však nevšímali žiadnych iných lemingov a zaujíma nás, či ich polohu vieme napriek tomu určiť.

Koľko informácie teda vieme odvodiť z toho, že jeden leming stojí pred cieľom? V skutočnosti pomerne veľa. Ako sme si ukázali už v podúlohe a., to že sa tento leming dostal až na koniec znamená, že sa pred ním vždy musel objaviť most, aby po ňom prešiel a dostal sa ďalej. Tým pádom poznáme niekoľko posledných písmen, ktoré boli vyslovené. Úplne presne, vieme, že tieto písmená boli postupne všetky písmená z jám.

A to nám už stačí na vyriešenie celej úlohy. Uvedomme si totiž, že ak sa nejaký leming nachádza niekde uprostred cesty, tak sa zo štartu vynoril neskôr ako leming stojaci pri cieli. Tým pádom všetky písmená, ktoré tento leming za svojho života počul, počul aj leming pri cieli. A síce nevieme, či tam skutočne je, vieme si odvodiť, čo by počul keby tam bol a skontrolovať či to sedí s jamami, ponad ktoré musel prejsť.

Ukážme si to trochu konkrétnejšie. Nech sa v jamách postupne nachádzajú písmená \(j_1, j_2 \dots j_n\). To sú zároveň aj posledné písmená, ktoré boli vyslovené. Teraz by sme chceli zistiť, či sa za prvou jamou nachádza leming. Ak by tam bol, tak počul posledné písmeno, ktoré bolo vyslovené, teda \(j_n\). Ale ponad prvú jamu mohol prejsť iba ak sa nad ňou objavil most, teda ak platilo, že \(j_1 = j_n\).

A čo s pozíciou za druhou jamou? Je tam leming? Postupujme úplne rovnako. Ak by tam bol, tak postupne počul písmená \(j_{n-1}\) a \(j_n\). Tieto písmená sa ale musia zhodovať s prvými dvoma jamami, teda znakmi \(j_1\) a \(j_2\).

Vyriešme teraz túto úlohu všeobecne. Označme si \(j[zac:kon]\) slovo, ktoré dostaneme zo slova \(j\) ak vyberieme iba písmená na pozíciách \(zac\) až \(kon\). Napríklad ak j = UURUURUU, tak j[2:5] = URUU a j[4:8] = UURUU. Potom platí, že za \(i\)-tou jamou je leming práve vtedy, ak j[n-i+1:n] (písmená, ktoré leming počul) a j[1:i] (jamy, nad ktorými musel prejsť) sú rovnaké.

V príklade na obrázku, kde je j = UURUURUU sa teda lemingovia nachádzajú za prvou jamou (j[1:1] = U = j[8:8]), druhou jamou (j[1:2] = UU = j[7:8]) a piatou jamou (j[1:5] = UURUU = j[4:8]). A samozrejme aj pred prvou, lebo tam je leming v podstate vždy.

Mimochodom, druhý možný prístup je, že ak poznáme všetky posledné písmená, ktoré boli vyslovené, môžeme jednoducho pochod lemingov odsimulovať a dostať sa tak k rovnakému riešeniu.

Hľadanie vzorky v texte

Pre zaujímavosť, všetko v tomto vzoráku úzko súvisí s hľadaním vzorky v texte. Úlohe, v ktorej máme v dlhom texte nájsť nejakú všetky výskyty kratšej vzorky, slova. V podstate klasická možnosť Find rôznych editorov. Dokonca, hrátky s lemingami vedú k optimálnemu riešeniu.

Základná myšlienka je rovnaká. Ak by sme simulovali pochod lemingov nad jamami s písmenami vzorky, ľahko nájdeme jej výskyty. Simulovať pohyb všetkých lemingov je však pomalé, oveľa jednoduchšie je sledovať len jedného, ktorý je najbližšie k cieľu. Tento leming sa totiž posunie dopredu ak sa ďalšie písmeno textu zhoduje s jamou, ktorá je pred ním, alebo padne a umrie. Jediný problém nastane, ak leming umrie. V tomto momente totiž musíme nájsť najbližšieho živého leminga, aby sme ho začali sledovať.

A pri tom vieme využiť podúlohu c. Vidíme totiž, že zo znalosti pozície niektorého leminga vieme zistiť, kde sa nachádzajú tí za ním. A dokonca to nesúvisí s textom, ktorý čítame, pretože ten je určený pozíciou nami sledovaného leminga. Túto informáciu si teda vieme vypočítať ešte pred tým, ako začneme čítať text. V podstate nás bude pre každú pozíciu zaujímať: Ak je na tejto pozícii živý leming, kde naľavo od neho je najbližší živý leming?

S touto informáciou je potom posúvanie leminga počas čítania textu jednoduché. Ak ide dopredu, tak ho proste posunieme a ak umrie, tak sa pozrieme do našej predpočítanej tabuľky aby sme zistili, ktorý leming ho nahradí.

Samozrejme, samotný algoritmus je ešte o niečo komplikovanejší, existuje napríklad spôsob ako si túto tabuľku predpočítať naozaj efektívne bez toho, aby sme simulovali celý proces, toto sú však hlavné myšlienky, ktoré sa v riešení používajú. V prípade, že by ste si chceli o tom prečítať viac, tento algoritmus sa volá KMP (podľa tvorcov Knuth, Morris a Pratt) a článok o ňom nájdete aj v KSP kuchárke.

Podúloha d.

Situácia, ktorú potrebujeme vyriešiť, vyzerá nasledovne:

Nepoznáme písmená v jamách a jediné čo vieme sú pozície dvoch najpravejších lemingov. Ako zistíme, či sú lemingovia aj za siedmou a jedenástou jamou? Postup z podúlohy c. nám nepomôže, pretože nepoznáme písmená a teda nevieme odsimulovať ako sa lemingovia hýbali.

Uvedomme si, že situácie sa v lemingove opakujú a sú závislé iba na tom, aké písmená sme čítali. To znamená, že vždy keď prečítame celé slovo z jám a leming sa ocitne pred cieľom, teda za sedemnástou jamou, bude najbližšie k nemu leming za dvanástou jamou. Pozícia leminga pred cieľom totiž presne určuje čo počul leming za jamou 12 a tieto písmená sú stále rovnaké. Dokonca, z podúlohy c. vieme povedať, že ak si slovo z jám označíme S, tak platí S[1:12] = S[6:17].

Predstavme si, že situáciu z obrázku chceme zopakovať, pokúsime sa teda leminga za 12 jamou dostať na koniec. Najbližších päť písmen budeme teda hovoriť presne to, čo potrebuje, aby sa mu vytvoril most. Nevadí, že tie písmená teraz nepoznáme, nám stačí len to, že by sme to vedeli spraviť, keby sme ich poznali, teda že taká možnosť existuje.

V okamihu ako sa tento leming ocitne pred cieľom, tak za 12 jamou sa musí objaviť nový leming. Lebo ak je na konci, tak situácia sa musí opakovať s tým, čo vidíme na pôvodnom obrázku. Z otáznikov sa teda po piatich písmenách vynoril leming a postavil sa za 12 jamu. Kde však tento leming začínal? Vráťme sa o 5 krokov späť a tento leming stojí za 7 jamou. Ukázali sme si teda, že za siedmou jamou sa musel nachádzať leming. Dokonca, rovnakým postupom by sme vedeli odôvodniť, že aj za druhou jamou je leming – to bude totiž ten, ktorý sa po piatich písmenách postaví za siedmu jamu.

Môže byť leming za jamou 11? Pozrime sa, čo by to znamenalo, keby tam bol. Posledné prečítané písmeno muselo vytvoriť most nad jamami 12 aj 11, obaja totiž prežili a prešli po nej. Teda S[11] = S[12]. Vráťme sa teda o krok dozadu. Opäť musí platiť, že posledné písmeno vytvorilo most aj nad 11 aj nad 10 jamou, teda S[10] = S[11]. Tento postup však môžeme opakovať až do úplného začiatku. Z toho vyplýva, že všetky písmená v jamách 1 až 12 musia byť rovnaké. Na začiatku sme si však uvedomili, že S[1:12] = S[6:17], tým pádom S[12] = S[17], S[11] = S[16] … S[1] = S[6]. Teda nie len prvých 12 písmen v jamách je rovnakých, všetky písmená sú rovnaké.

To však nie je možné, ak by totiž všetky písmená boli rovnaké, tak ak sa nejaký leming dostane až k cieľu, za každou jednou jamou sa musí nachádzať leming. Nestalo by sa teda, že za jamami 13 až 16 by žiadni neboli. Tým pádom, chyba musí byť v našom predpoklade. Za jamou 11 sa leming nemôže nachádzať.

Podúloha e.

Ostáva nám nájsť najkratšiu periódu zadaného reťazca. Perióda dĺžky \(p\) je definovaná tak, že každá dvojica písmen vzdialených od seba o \(p\) písmen je rovnaká. Teda musí platiť, že S[i] = S[i+p] pre všetky možné \(i\), čo sú všetky čísla od 1 po \(n-p\). To sa však dá napísať aj tak, že S[1:n-p] = S[p+1:n]. Takýto zápis sme však už niekde videli nie? Toto bol presne zápis, ktorým sme zisťovali, či sa za jamou \(n-p\) nachádza leming, ak je ďalší leming pri cieli.

Vidíme teda, že z pozícií dvoch posledných lemingov vieme určiť periódu celého textu. Stačí si odsimulovať pochod lemingov v prípade, že postupne čítame písmaná, ktoré sa nachádzajú nad jamami. Keď sa najpravejší leming nachádza pred domčekom, pozrieme sa, kde je k nemu najbližší živý leming. Počet jám medzi nimi udáva periódu celého reťazca. Táto perióda je navyše najkratšia možná.

Napriek tomu ako jednoducho správanie lemingov vyzeralo, pomohlo nám odvodiť si pomerne široké závery o reťazcoch všeobecne. Nielenže sme dokázali hľadať vzorku v texte, dokázali sme dokonca zistiť aj periódu zadaného reťazca.