vyhľadávanie podreťazca v reťazci
reťazec S[n], podreťazec T[m] triviálne všetky možné začiatky umiestnenia podreťazca, kontrolujeme celý podreťazec
$(n-m+1) \cdot m = O(n \cdot m)$
rolling hash https://paz1b-old.ics.upjs.sk/files/prednasky/prednaska9.pdf
modulárny súčet/crc/na paz1b ste mali zápis v sústave so základom 123
jedno písmeno odstránime a jedno pridáme na výpočet ďalšej hodnoty
ak sa líši hash, tak sú rôzne slová ... pri zhode ešte treba skontrolovať písmeno po písmene
modulárny súčet ... hash(ABC)=hash(BBB)
ak nevznikne kolízia, tak $O(n+m)$
najdlhšia spoločná vybraná podpostupnosť Longest Common Subsequence
DNA/RNA
dynamické programovanie https://paz1b-old.ics.upjs.sk/files/prednasky/prednaska7.pdf#47
hľadanie viacerých slov naraz
$S[n], T_1[m_1], \dots, T_k[m_k]$
dopĺňanie textu (pri vyhľadávaní/autocomplete pri programovaní, terminál)
vstup ... reťazec $S[n]$ (prefix), zoznam slov $[T_1, T_2, \dots, T_k]$
výsledok ... všetky reťazce začínajúce na $S$
trie, prefixový)¶zobraz_trie(['ahoj', 'asu', 'ahojte', 'upjs', 'trie', 'trieda', 'trik'])
efektívne uloženie slovníka, vyhľadávanie slova aj slov začínajúcich na zadaný prefix - automatické dopĺňanie/našepkávanie (vo vyhľadávači automaticky po napísaný nejakého textu, v programovacom prostredí ctrl+medzera, v shell-i tabulátorom)
http://oi.sk/archiv/2010/sl-2010-3-zad-day1.pdf
5
prasa
pomysel
ziari
tvari
zabronel
3
krasa
zmari
bager
prasa
tvari
pomysel
https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
ananas, kalika
Na vstupe je dlhý reťazec $T$. Potom bude prichádzať veľa ďalších reťazcov. O každom z nich zistite, či sa v $T$ nachádza ako podreťazec.
Zostrojíme si sufixový strom pre $T$. Následne pre každý reťazec $S$ začneme v koreni stromu a snažíme sa ísť dodola cestou, ktorá zodpovedá $S$. Ak sa nám to podarí, vieme, že $S$ sa v $T$ nachádza, ak sa niekde zasekneme, vieme, že nastal opačný prípad. Každý reťazec takto spracujeme v čase lineárnom od jeho dĺžky.
Na vstupe je dlhý reťazec $T$. Potom bude prichádzať veľa ďalších reťazcov. O každom z nich zistite, koľkokrát sa v $T$ nachádza ako podreťazec.
Po tom, ako sufixový strom zostrojíme, ho rekurzívne prejdeme a v každom vrchole si spočítame, koľko sufixov pod ním končí (vrátane jeho samotného). Rozmyslite si, že keď máme v našom sufixovom strome vrcholr zodpovedajúci reťazcu $R$, tak každý koniec sufixu v podstrome s koreňom $r$ zodpovedá jednému výskytu reťazca $R$ v pôvodnom texte.
V premennej $strom$ je sufixový strom nejakého neznámeho reťazca. Napíšte čo najefektívnejší program, ktorý zistí, koľko navzájom rôznych písmen tento reťazec obsahuje.
Príklad: Ak ide o reťazec macka, odpoveďou by malo byť číslo 4.
Na vstupe je daný reťazec $S$. Napíšte program, ktorý v optimálnej časovej zložitosti nájde (jeden ľubovoľný) najdlhší podreťazec $T$, ktorý sa v $S$ vyskytuje aspoň dvakrát. Výskyty $T$ v $S$ sa môžu čiastočne prekrývať.
Príklady: Pre rokoko je riešením oko. Pre macka je riešením a. Pre pes je riešením prázdny reťazec ``.
Na vstupe je daný reťazec $S$. Napíšte program, ktorý v optimálnej časovej zložitosti spočíta, koľko má $S$ navzájom rôznych podreťazcov.
Príklad: Pre rokoko je správna odpoveď 15. V abecednom poradí sú to nasledovné podreťazce: k,ko,kok,koko,o,ok,oko,okok,okoko,r,ro,rok,roko,rokok a rokoko. (Niektoré z nich sa v $S$ vyskytujú viackrát.)
Na vstupe sú dané reťazce $S$ a $T$ tvorené malými písmenami anglickej abecedy. Napíšte program s optimálnou časovou zložitosťou, ktorý nájde jeden ich najdlhší spoločný podreťazec. Inými slovami, hľadáme najdlhší reťazec $R$ ktorý sa vyskytuje ako (súvislý) podreťazec aj v $S$, aj v $T$.
Napr. pre $S=$ kalerab a $T=$prales je jediným správnym riešením reťazec ale.
Hovoríme, že reťazecAmá periódu dĺžky $p$, ak pre všetky relevantné $i$ platí $A[i] =A[p+i]$. Napríklad reťazec $A=$ mamam má periódu dĺžky 2, lebo platí $A[0] =A[2],A[1] =A[3]$ aj $A[2] =A[4]$. Ďalšie príklady: Najkratšia perióda reťazca eeee je 1. Najkratšia perióda reťazca hahaha je 2. Najkratšia perióda reťazca koliesko je 6. Najkratšia perióda reťazca banan je 5.
V premennej $strom$ je sufixový strom nejakého neznámeho reťazca. Slovne popíšte algoritmus, ktorý priamo z tohto stromu vypočíta dĺžku najkratšej periódy dotyčného reťazca.
Určite poznáte osemsmerovku: logickú úlohu, pri ktorej lúštení je potrebné nájsť nejaké slová v danej tabuľke písmen. Možno ste si ale neuvedomili, že množina slov, ktoré treba v osemsmerovke vyškrtať, nemôže byť len tak hocijaká. Okrem iného musí platiť, že žiadne z vyškrtávaných slov nie je podreťazcom iného z nich. Napríklad v dobrej osemsmerovke nebudú naraz slová tvor a potvora. Totiž potom by sa mohlo stať, že v osemsmerovke nájdem slovo tvor, vyškrtnem ho, ale potom sa ukáže, že to nebol ten správny tvor, ale časť dlhšieho slova potvora. Na vstupe sú dané reťazce $S_1, \dots, S_n$. Napíšte program s optimálnou časovou zložitosťou, ktorý zistí, či je niektorý z týchto reťazcov podreťazcom iného.
Vytvoríme si sufixový strom zo slova $S_1\#S_2\#\dots\#S_n$ ... vieme vyhľadať $S_i$ ? Využitím príkladu 2 zo zadania nám stačí overiť či počet výskytov je väčší ako jedna ... vtedy sa vyskytuje zvlášť slovo $S_i$, ako aj podreťazec iného slova $S_j$.
Cyklický posun reťazca je každý reťazec, ktorý vieme vyrobiť tak, že pôvodný reťazec rozdelíme na dve časti a druhú presunieme pred prvú. Napr. všetky cyklické posuny reťazca zabka sú zabka,abkaz,bkaza,kazab a azabk. Keby sme tieto cyklické posuny usporiadali podľa abecedy, dostaneme nasledovné poradie: abkaz,azabk,bkaza,kazab,zabka.
Daný je reťazec $S$ dĺžky $n$ a číslo $k$, pre ktoré platí $1≤k≤n$. Napíšte program s optimálnou časovou zložitosťou,ktorý vypíše $k$-ty najmenší cyklický posun reťazca $S$. Napr. pre $S=$ zabka a $k= 4$ by mal byť výstupom reťazec kazab. Pre $S=$ baba by aj pre $k= 1$ aj pre $k= 2$ mal byť výstupom reťazec abab.