X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=6-kmp%2F6-kmp.tex;h=bfcef05247e9a0d0296590fbc81d2a2ca5d4def5;hb=ef9ea0e2dba1f4450881e763524cf9f2fbc100bb;hp=08f4edac1b00022e1addfc68ca33d5cc94e52aae;hpb=1b76f55dbcd7e4e4f104f9d855ecf698b2670593;p=ads2.git diff --git a/6-kmp/6-kmp.tex b/6-kmp/6-kmp.tex index 08f4eda..bfcef05 100644 --- a/6-kmp/6-kmp.tex +++ b/6-kmp/6-kmp.tex @@ -2,13 +2,14 @@ \prednaska{6}{Vyhledávání v textu}{(zapsal K. Ka¹èák, M. Klauèo, M. Vachna)} -\s{Úkol:} V~textu s~délkou $S$ najít v¹echny výskyty hledaného slova s~délkou $J$ (hledaných slov). +\s{Úkol:} V~textu s~délkou $S$ najít v¹echny výskyty hledaného slova s~délkou $J$. \h{Hloupý algoritmus} -Algoritmus prochází sekvenènì textem a hledaným vzorovým slovem. Pøi neshodì se ve vzorovem slovì vrací na zaèátek a v~textu pokraèuje znakem, v~kterém nastala neshoda. Èasová slo¾itost je $\O(S)$. Tento algoritmus funguje pouze jen pro vzorová slova bez opakujících se znakù. +Algoritmus prochází sekvenènì textem a hledaným vzorovým slovem. Pøi neshodì se ve vzorovem slovì vrací na zaèátek a v~textu pokraèuje znakem, ve~kterém nastala neshoda. Èasová slo¾itost je $\O(S)$. Tento algoritmus funguje pouze pro vzorová slova, ve kterých se neopakuje první znak. -\s{Pøíklad:} Hledání vzorového slova |jehla| v~textu |vkupcejejehla|. Ve chvíli kdy máme prefix |je| a na vstupu dostaneme |j|, dochází k~neshodì a pokraèujeme v~hledání od tohoto znaku. +\s{Pøíklad:} Hledání vzorového slova |jehla| v~textu |vkupcejejehla|. Ve chvíli kdy máme prefix |je| a na vstupu dostaneme |j|, dochází k~neshodì a pokraèujeme v~hledání od tohoto znaku. Pro tenhle pøípad algoritmus najde vzorové slovo. To ale ji¾ neplatí +pro vzorové slovo |kokos| v~textu |clanekokokosu|. Ve chvíli kdy máme prefix |koko| a na vstupu dostaneme |k|, dochází k~neshodì a pokraèujeme v~hledání od tohoto znaku, tím ale zahodíme potøebnou èást a algoritmus sel¾e. \h{Neefektivní algoritmus} @@ -16,112 +17,105 @@ Algoritmus proch \h{Chytrý algoritmus} -Algoritmus je vylep¹ením Neefektivního algoritmu, konkretnì zpùsobu jakým sa vrací v textu pøi neshodì mezi znakem textu a +Algoritmus je vylep¹ením Neefektivního algoritmu, konkrétnì zpùsobu, jakým sa vrací v textu pøi neshodì mezi znakem textu a znakem vzorového slova. -\s{Pøíklad:} Pro vzorové slovo |ajaajak| jsme na¹li v~textu prefix |ajaaja|. Oèakávame |k|. +\s{Pøíklad:} Pro vzorové slovo |ajaajak| jsme na¹li v~textu prefix |ajaaja|. Oèekávame |k|. \itemize\ibull \:Kdy¾ ale dostaneme |a| a budeme mít prefix |ajaajaa|, vracíme se v~textu za první |aja|, tedy prefix zkrátíme na |ajaa| a pokraèujeme v~hledání. \:Kdy¾ je nasledující znak |j| a budeme mít prefix |ajaajaj|, vracíme se v~textu za |ajaaj|, tedy prefix zkrátíme na |aj| a pokraèujeme v~hledání. -\:V~pøípadì, ¾e dostaneme jiný znak, v~textu se nevracíme a pokraèujeme dal¹ím znakem v~textu. +\:V~pøípadì, ¾e dostaneme jiný znak, se v~textu nevracíme a pokraèujeme dal¹ím znakem textu. \endlist \s{Definice a znaèení pro øetìzce (slova):} -\itemize\ibull + \s{Definice:} \itemize\ibull -\:{\I Abeceda $\Sigma$} je koneèná mno¾ina znakù, ze kterých tvoøíme text, øetìzece, slova jako koneèné posloupnosti znakù ze $\Sigma$. Pøíkladem extrémních abeced je binární abeceda slo¾ená z~nul a jednièek. Pøíklad z~druhého konce je abeceda, která má jako znaky slova èeského jazyka. V algoritmech nebudeme uva¾ovat velikost abecedy (poèet znakù). -\:{\I $\Sigma$*} je mno¾ina v¹ech slov nad abecedou $\Sigma$. +\:{\I Abeceda $\Sigma$} je koneèná mno¾ina znakù, ze~kterých tvoøíme text, øetìzce, slova jako koneèné posloupnosti znakù z $\Sigma$. Pøíkladem extrémních abeced je binární abeceda slo¾ená z~nul a jednièek. Pøíklad z~druhého konce je abeceda, která má jako znaky slova èeského jazyka. V algoritmech nebudeme uva¾ovat velikost abecedy (poèet znakù), budeme pøedpokládat, ¾e je to konstanta. +\:{\I $\Sigma^*$} je mno¾ina v¹ech slov nad abecedou $\Sigma$. \endlist \s{Znaèení:} \itemize\ibull -\:{\I Slova} budeme znaèit malými písmeny øecké abecedy $\alpha$, $\beta$, \dots, -\:{\I Znaky} velkými písmeny latinky $A$, $B$, \dots +\:{\I Slova} budeme znaèit malými písmeny øecké abecedy $\alpha$,$\beta$... a {\I znaky} malými písmeny latinky $a$,$b$... . \:{\I Prázdné slovo} znaèíme písmenem $\varepsilon$. -\:{\I Délka slova} $\vert \alpha \vert$ pro $\alpha \in \Sigma^*$ je poèet znakù. -\:{\I Zøetìzení} $\alpha\beta$ vznikne zapsáním slov $\alpha$ a $\beta$ za sebe. Platí: $\alpha\varepsilon=\varepsilon\alpha=\alpha$, $\vert \alpha\beta \vert=\vert \alpha \vert+\vert \beta \vert$. +\:{\I Délka slova} $\vert \alpha \vert$ pro $\alpha \in \Sigma^*$ je poèet jeho znakù. +\:{\I Zøetìzení} $\alpha\beta$ vznikne zapsáním slov $\alpha$ a $\beta$ za sebe. Platí $\alpha\varepsilon=\varepsilon\alpha=\alpha$, $\vert \alpha\beta \vert=\vert \alpha \vert+\vert \beta \vert$. \:$\alpha[i]$ je $i$-té písmeno slova $\alpha$, indexuje se od $0$. -\:$\alpha[i:j]$ je podslovo tvoøené písmeny $\alpha[i]$,...,$\alpha[j-1]$. Pøíklady: $\alpha[i:i+1]=\alpha[i]$, $\alpha[i:i]=\varepsilon$, $\alpha[:]=\alpha$. -\:$\alpha[:j]$ je prefix obsahující prvních $j$ znakù slova $\alpha$. -\:$\alpha[i:]$ je suffix obsahující znaky slova $\alpha$ poèínaje $i$-tým znakem. -\:Ka¾dé slovo je prefixem i suffixem sebe sama, takovému prefixu resp. suffixu øíkáme {\I nevlastní}. V¹em ostatním {\I vlastní}. +\:$\alpha[i:j]$ je podslovo tvoøené písmeny $\alpha[i]$,...,$\alpha[j-1]$. Pøíklady: $\alpha[i:i+1]=\alpha[i]$, $\alpha[i:i]=\varepsilon$. Vynechaním první meze získame prefix ($\alpha[:j]$), druhé meze suffix ($\alpha[i:]$), obou mezí dostaneme celé slovo ($\alpha[:]$=$\alpha$). +\:$\alpha[:j]$ je {\I prefix} obsahující prvních $j$ znakù slova $\alpha$. +\:$\alpha[i:]$ je {\I suffix} obsahující znaky slova $\alpha$ poèínaje $i$-tým znakem. +\:Ka¾dé slovo je prefixem i suffixem sebe sama, takovému prefixu/suffixu øíkáme {\I nevlastní}. V¹em ostatním {\I vlastní}. \:Prázdné slovo je podslovem, prefixem i suffixem ka¾dého slova vèetnì prázdného slova. \endlist -\endlist -\s{Problém:} -\itemize\ibull -\s{IN:} -\itemize\ibull -\:$\iota$ slovo (jehla) délky $J=\vert \iota \vert$, -\:$\sigma$ text (seno) délky $S=\vert \sigma \vert$. -\endlist -\s{OUT:} -\itemize\ibull -\:V¹echny výskyty slova $\iota$ v textu $\sigma$: $\left\{ i : \sigma[i:i+J]=\iota \right\}.$ -\endlist -\endlist + +\s{Problém:} + +Vstupem je $\iota$ hledané slovo (jehla) délky $J=\vert \iota \vert$ a $\sigma$ text (seno) délky $S=\vert \sigma \vert$. + +Výstupem jsou v¹echny vyskyty hledaného slova $\iota$ v textu $\sigma$: $\left\{ i\vert \sigma[i:i+J]=\iota \right\}$ \h{Vyhledávací automat (Knuth, Morris, Pratt)} -Vyhledávací automat bude vlastnì graf, jeho¾ vrcholy reprezentují stavy. Jmény stavù budou v¹echny prefixy slova $\iota$. Poèáteèní stav je prázdné slovo $\varepsilon$ a koneèný je samotná $\iota$. Dopøedné hrany grafu budou popisovat pøechod mezi stavy ve smyslu zvìt¹ení délky jména stavu (dopøedná funkce $d(\alpha , X)$), tedy ka¾dá taková hrana bude oznaèena písmenem $X$ a bude popisovat dané zvìt¹ení délky jména stavu, tedy $\alpha \rightarrow \alpha X$. Zpìtné hrany grafu budou popisovat pøechod (zpìtná funkce $z(\alpha)$) mezi stavem $\alpha$ a nejdel¹ím vlastním suffixem $\alpha$, který je prefixem $\iota$, kdy¾ nastane neshoda. +Vyhledávací automat bude graf, jeho¾ vrcholùm øíkame stavy automatu. Jména stavù budou v¹echny prefixy slova $\iota$. Poèáteèní stav je prázdné slovo $\varepsilon$ a koncový je celá $\iota$. Dopøedné hrany grafu budou popisovat pøechod mezi stavy ve~smyslu zvìt¹ení délky jména stavu (dopøedná funkce $d(\alpha , X)$), tedy ka¾dá taková hrana bude oznaèena písmenem $X$ a bude popisovat dané zvìt¹ení délky jména stavu, tedy $\alpha \rightarrow \alpha X$. Zpìtné hrany grafu budú popisovat pøechod (zpìtná funkce $z(\alpha)$) mezi stavem $\alpha$ a nejdel¹ím vlastním suffixem $\alpha$, který je prefixem $\iota$, kdy¾ nastane neshoda. \figure{vautomat.eps}{Vyhledávací automat}{5.5in} -\s{Vyhledávaní:} +\s{Vyhledávání:} \algo \:$\alpha \leftarrow \varepsilon$. -\:Pro $C\in\sigma$ postupnì: -\::Dokud $\neg \exists d(\alpha , C) \wedge \alpha\neq\varepsilon$: $\alpha \leftarrow z(\alpha)$. -\::Pokud $\exists d(\alpha , C)$: $\alpha \leftarrow d(\alpha , C)$. -\::Pokud $\alpha = \iota$: vrátíme, ¾e hledané slovo je v~textu. +\:Pro $c\in\Sigma$ postupnì: +\:$\indent$Dokud $\neg \exists d(\alpha , c) \wedge \alpha\neq\varepsilon : \alpha \leftarrow z(\alpha)$. +\:$\indent$Kdy¾ $\exists d(\alpha , c)\Rightarrow \alpha \leftarrow d(\alpha , c)$. +\:$\indent$Kdy¾ $\alpha = \iota \Rightarrow$ hledané slovo je v~textu. \endalgo -\s{Alternativa:} +\s{Alternatíva:} Automat mù¾e být reprezentovaný i polem. Pøi této reprezentaci odpadá starost o dopøední hrany (staèí zvìt¹it hodnotu, kterou v poli indexujeme). Hodnota na dané pozici v poli urèuje kam smìruje zpìtná hrana (index v poli). + +\s{Alternatívní vyhledávání:} \algo \:$k \leftarrow 0$. -\:Pro $C\in\sigma$ postupnì: -\::Dokud $C\neq \iota[k] \wedge k>0$: $k \leftarrow z(k)$. -\::Pokud $C=\iota[k]$: $k \leftarrow k+1$. -\::Pokud $k = J$: vrátíme, ¾e hledané slovo je v~textu. +\:pro $c\in\Sigma$ postupnì: +\:$\indent$Dokud $c\neq \iota[k] \wedge k>0: k \leftarrow z[k]$ +\:$\indent$Je-li $c=\iota[k] \Rightarrow k \leftarrow k+1$ +\:$\indent$Kdy¾ $k = J \Rightarrow$ hledané slovo je v~textu \endalgo -\s{Invariant:} Stav po pøeètení vstupu $\beta$: $\alpha(\beta)$ je nejdel¹í suffix $\beta$, který je prefixem $\iota$. -Z~invariantu vyplývá korektnost vyhledávací èásti algoritmu KMP. +\s{Invariant:} Nejdel¹í suffix $\beta$, který je prefixem $\iota$ $=$ $\alpha(\beta)$. Kde $\beta$ je pøeètení vstup. +Z~invariantu vyplýva korektnost vyhledávací èásti algoritmu KMP. \proof -Dùkaz indukcí. Na zaèátku pro prázdný naètený vstup platí invariant, tedy prázdný suffix $\beta$ je prefixem $\iota$. V~kroku $n$ máme naètený vstup $\beta$ a k~nìmu naèteme znak $C$. Jestli¾e si odmyslíme $C$, tedy kdy¾ si od jména stavu odmyslíme poslední písmenko, dostaneme znovu jméno stavu. Tak stav, který pasuje na konec vstupu bez toho $C$, je stavem, který pasuje na konec pùvodního vstupu, toho o~jeden znak krat¹ího. Tím pádem to musí být nìco, co je maximálnì tak dlouhé jako pùvodní stav, u~kterého jsme byli, proto¾e to byl nejdel¹í, který pasoval. Staèí procházet postupnì v¹echny stavy, které pasují na konec toho vstupu od nejdel¹ího k~nejkrat¹ímu a vzít první, který se dá roz¹íøit o $C$. To je pøesnì to, co algoritmus dìlá, proto¾e zpìtná funkce øekne nejbli¾¹í krat¹í jméno stavu. Tak¾e algoritmus iteruje pøes stavy, které tam pasují, a¾ najde jeden, který se dá roz¹íøit o~$C$, a jeliko¾ iteroval od nejdel¹ího, tak to je logicky ten nejdel¹í, který tam pasuje. +Indukcí podle $\vert \beta \vert$. Na zaèátku pro prázdný naètený vstup platí invariant, tedy prázdny suffix $\beta$ je prefixem $\iota$. V~kroku $n$ máme naètený vstup $\beta$ a k~nìmu naèteme znak $c$. Jestli si odmyslíme $c$, tedy kdy¾ si od jména stavu odmyslíme poslední písmenko, dostaneme znovu jméno stavu. Tak stav, který pasuje na konec vstupu bez toho $c$ je stav, který pasuje na konec pùvodního vstupu, toho o~jeden znak krat¹ího. Tím pádem to musí být nìco, co je maximálnì tak dlouhé jako pùvodní stav, u~kterého jsme byli, proto¾e to byl nejdel¹í, který pasoval. Staèí procházet postupnì v¹echny stavy, které pasují na konec toho vstupu od nejdel¹ího k~nejkrat¹ímu a vzít první, který se dá roz¹íøit o $c$. To je pøesnì to, co algoritmus dìlá. Proto¾e zpìtná funkce øekne nejbli¾¹í krat¹í jméno stavu. Tak¾e algoritmus iteruje pøes stavy, které tam pasují, a¾ najde jeden, který se dá roz¹íøit o~$c$ a jeliko¾ iteroval od toho nejdel¹ího, tak to je logicky ten nejdel¹í, který tam pasuje. \qed -\s{Lemma:} Vyhledávaní dobìhne v~èase $\O(S)$. +\s{Lemma:} Vyhledávání dobìhne v~èase $\O(S)$. \proof -Pro ka¾dý znak vstupního textu mohou nastat dva pøípady. Znak roz¹iøuje aktuální prefix, nebo musíme pou¾ít zpìtnou funkci (zpìtnou hranu). Roz¹irování trvá konstantnì mnoho èasu, zatímco zpìtná funkce mu¾e být pro jeden znak volána a¾ $J$-krát. Pøi ka¾dém volání klesne délka aktuálního stavu minimálnì o~jedna a zároveò platí, ¾e kdykoliv stav prodlu¾ujeme, roste právì o~jeden znak. Proto v¹ech zkrácení dohromady mu¾e být nejvý¹e tolik, kolik bylo v¹ech prodlou¾ení, t.j. kolik jsme pøeèetli znakù textu. Celkem je tedy poèet krokù lineární vzhledem k~délce textu. +Pro ka¾dý znak vstupního textu mohou nastat dva pøípady. Znak roz¹iruje aktuální prefix, nebo musíme pou¾ít zpìtnou funkci (zpìtnou hranu). Roz¹irování trvá konstantnì mnoho èasu, zatímco zpìtná funkce mu¾e být pro jeden znak volána a¾ $J$-krát. Pøi ka¾dém volání klesne délka aktuálního stavu minimálnì o~jedna a zároveò platí, ¾e kdykoliv stav prodlu¾ujeme, roste právì o~jeden znak. Proto v¹ech zkrácení dohromady mu¾e být nejvý¹e tolik, kolik bylo v¹ech prodlou¾ení, t.j. kolik jsme pøeèetli znaku textu. Celkem je tedy poèet krokù lineární vzhledem k~délce textu. \qed \s{Konstrukce zpìtné funkce:} \algo -\:Sestrojíme dopøedné hrany. -\:$z( \varepsilon ) \leftarrow \emptyset$, $z( \iota [0]) \leftarrow \varepsilon $. -\:$\alpha \leftarrow \varepsilon$. -\:Pro $i = 1$ do $J-1$: -\:$\indent$$\alpha \leftarrow krok( \alpha , \iota [i])$. -\:$\indent$$z( \iota [0:i+1]) \leftarrow \alpha$. +\:Sestrojíme dopøedné hrany +\:$z( \varepsilon ) \leftarrow 0$, $z( \iota [0]) \leftarrow \varepsilon $ +\:$\indent$ $\alpha \leftarrow \varepsilon$ +\:pro $i = 1$ do $J$ +\:$\indent$$\alpha \leftarrow krok( \alpha , \iota [i])$ +\:$\indent$$z( \iota [0:i+1]) \leftarrow \alpha$ \endalgo -\s{Vysvìtlení:} V¹imnìte si, ¾e $z(i)$ je pøesnì stav, do nìho¾ se dostaneme pøi spu¹tìní na¹eho vyhledávacího algoritmu na øetìzec $\iota [2:i]$, èili na $i$-tý prefix bez prvního písmenka. Proè to tak je? Zpìtná funkce øíká, jaký je nejdel¹í vlastní suffix daného stavu, který je také stavem, zatímco $\alpha$ oznaèuje nejdel¹í suffix textu, který je stavem. Tyto dvì vìci se pøeci li¹í jen v~tom, ¾e ta druhá pøipou¹tí i nevlastní suffixy, a právì tomu zabráníme odstranìním prvního znaku. Tak¾e $z()$ získáme tak, ¾e spustíme vyhledávání na èást samotného slova $\iota$. Jen¾e k~vyhledávání zase potøebujeme zpìtnou funkci $z$. Proto budeme zpìtnou funkci vytváøet postupne od nejkrat¹ích prefixu. Zøejmì $z(1) = \varepsilon$. Pokud ji¾ máme $z(i)$, pak výpoèet $z(i+1)$ odpovídá spu¹tení automatu na slovo délky i a pritom budeme zpìtnou funkci potøebovat jen pro stavy délky $i$ nebo men¹í, pro které ji ji¾ máme hotovou. +\s{Vysvìtlení:} V¹imnìte si, ¾e $z(i)$ je pøesnì stav, do nej¾ se dostaneme pøi spu¹tìní na¹eho vyhledávacího algoritmu na øetìzec $\iota [2:i]$, èili na $i$-tý prefix bez prvního písmenka. Proè to tak je? Zpìtná funkce øíká, jaký je nejdel¹í vlastní suffix daného stavu, který je také stavem, zatímco $\alpha$ oznaèuje nejdel¹í suffix textu, který je stavem. Tyto dvì vìci se pøeci li¹í jen v~tom, ¾e ta druhá pøipou¹tí i nevlastní suffixy, a právì tomu zabráníme odstranìním prvního znaku. Tak¾e $z()$ získáme tak, ¾e spustíme vyhledávání na èást samotného slova $\iota$. Jen¾e k~vyhledávání zase potøebujeme zpìtnou funkci $z$. Proto budeme zpìtnou funkci vytváøet postupne od nejkrat¹ích prefixù. Zøejmì $z(1) = \varepsilon$. Pokud ji¾ máme $z(i)$, pak výpoèet $z(i+1)$ odpovídá spu¹tení automatu na slovo délky $i$ a pritom budeme zpìtnou funkci potøebovat jen pro stavy délky $i$ nebo men¹í, pro které ji ji¾ máme hotovou. Navíc nemusíme pro jednotlivé prefixy spou¹tìt výpoèet v¾dy znovu od zaèátku, proto¾e $(i+1)$-ní prefix -je prodlou¾ením $i$-tého prefixu o~jeden znak. Staèí tedy spustit algoritmus na celý øetìzec $\iota[1:J]$ a sledovat, jakými stavy bude procházet. A to budou pøesnì hodnoty zpìtné funkce. Vytvoøení zpìtné funkce se tak nakonec zredukovalo na jediné vyhledávání v~textu o~délce $J-1$, a proto pobe¾í v case $\O(J)$. Èasová slo¾itost celého algoritmu tedy bude $\O(S+J)$. +je prodlou¾ením $i$-tého prefixu o~jeden znak. Staèí tedy spustit algoritmus na celý øetìzec $\iota$ a sledovat, jakými stavy bude procházet. To budou pøesnì hodnoty zpìtné funkce. Vytvoøení zpìtné funkce se tak nakonec zredukovalo na jediné vyhledávání v~textu o~délce $J-1$, a proto pobì¾í v èase $\O(J)$. Èasová slo¾itost celého algoritmu tedy bude $\O(S+J)$. -\h{Algoritmus (Rabin, Karp)} -Tenhle algoritmus funguje tak, ¾e porovnává hash hledaného øetìzce s~hashem aktuálního podøetìzce v~textu a aktuální podøetìzec porovná se vzorkem pouze v~pøípadì, kdy¾ mají shodný hash. Kdy¾ si zvolíme tu správnou hashovací funkci, budeme moci vypoèítat hash následujíciho podøetìzce na základe hashe toho aktuálního. Jako hashovací funkci $h: \Sigma^J \rightarrow {\bb Z}$ pou¾ijeme následující: -$$h(x_{0},...,x_{J-1}) = ( \sum_{i=0}^{J-1} x_{i}.p^{J-i}) \bmod N,$$ -kde $N$ je velikost prostoru, do kterého hashujeme. Jak zjistíme hash $h{'}$ následujícího podøetìzce? +\h{Algoritmus Rabin \& Karp} +Tento algoritmus funguje tak, ¾e porovnává hash hledaného øetìzce s~hashem aktuálního podøetìzce (\uv{posuvné okénko} stejné délky jako hledaný øetìzec) v~textu a aktuální podøetìzec porovná se vzorkem pouze v~pøípadì, kdy¾ mají shodný hash. Kdy¾ si zvolíme tu správnou hashovací funkci, budeme moci vypoèítat hash následujíciho podøetìzce na základe hashe toho aktuálního. Jako hashovací funkci $h: \Sigma^J \rightarrow \bb Z$ pou¾ijeme následující: $h(x_{0},...,x_{J-1}) = ( \sum_{i=0}^{J-1} x_{i}.p^{J-1-i}) \bmod N$, kde $N$ je velikost prostoru, do kterého hashujeme. Jak zjistíme hash následujícího podøetìzce? \itemize\ibull \:$h = x_{0}.p^{J} + x_{1}.p^{J-1} + ... + x_{J-1}.p^{1}$ \:$h^{'} = x_{1}.p^{J} + x_{2}.p^{J-1} + ... + x_{J}.p^{1}$ \:$h^{'} = (h - x_{0}.p^{J}).p + x_{J}.p^{1}$ \endlist -Tady mù¾eme vidìt, ¾e hash následujícího øetìzce lze pøepoèítat na základì toho pøedchozího v konstantním èase. Èasová slo¾itost je v nejlep¹ím pøípadì lineární vzhledem k~délce textu, zatímco nejhor¹í pøípad mù¾e trvat $\O(JS)$. +Tady mù¾eme vidìt, ¾e hash následujícího øetìzce lze pøepoèítat na základì toho pøedchozího v konstantním èase. +Èasová slo¾itost je v nejlep¹ím pøípadì lineární vzhledem k~délce textu, zatímco nejhor¹í pøípad mú¾e trvat a¾ $\Theta(JS)$. \bye