\section{Rabin-Karp (1987)}
Majme hashovaciu funkciu $H:\Sigma^m \rightarrow \{0,1,\dots ,p-1
\}$. Na začiatku zahashujeme vzorku $P$ a potom jej zahashovanú formu
porovnávame so zahashovanými pozíciami v texte.

\begin{lstlisting}
hp = H(P)     // hashujeme vzorku P
for(i=0; i<=n-m; i++) {
  ht = H(T[i..i+m-1]);  // hashujeme potencialny vyskyt
  if(hp == ht) {        // ak sa hashe rovnaju
    if(P==T[i..i-m+1]) { // skontroluj, ci mame vyskyt
      write i;
    }
  }
}
\end{lstlisting}

Aby sme dostali efektívny algoritmus, potrebujeme splniť nasledujúce 
podmienky:
\begin{enumerate}
\item Hash by sa mal počítať v čase O($1$)
\item Chceme málo falošných zhôd takých, 
že $h_p = h_t \land P \neq T[i\dots i-m+1]$
\end{enumerate}
Slovo $S$ dĺžky $m$ reprezentujme ako číslo v sústave so základom $\sigma$: 
$\sum^{m-1}_{j=0}\sigma^{m-j-1}S[j]$. Napr. $(10011)_2 = 19$. 
Naša hashovacia funkcia bude  $H(S) = S \bmod p$.
Na počítanie budeme používať Hornerovu schému:
 $$S = ( (S[0]\sigma + S[1])\sigma + S[2])\sigma \dots$$

\begin{lstlisting}
int H(S,p,sigma){
   h = 0;
   for(i=0; i<|S|; i++) {
     h = h*sigma mod p;
     h = (h + S[i]) mod p;
   }
   return h;
}
\end{lstlisting}

Časová zložitosť tohto výpočtu je $O(|S|)$. Nech $H_i = H(T[i..i+m-1])$. 
Pre hľadanie v texte potrebujeme rýchlo vypočítať $H_i$ z už vypočítanej hodnoty $H_{i-1}$. Dostaneme, že $H_i = (\sigma(H_{i-1} - \sigma^{m-1}T[i-1])+T[i+m-1]) \bmod p$. Aby sme nemuseli pracovať s veľkými číslami,  $\sigma^{m-1}$ máme predpočítané tiež modulo $p$. 

Celková časová zložitosť Rabinovho-Karpovho algoritmu 
je $O(n + m(1+k+f))$, kde $k$ je počet výskytov a $f$ je počet falošných zhôd,
t.j. pozícií, kde $H(P)=H_i$, ale $P\ne T[i..i+m-1]$.

\subsection{Randomizovaná verzia Rabinovho-Karpovho algoritmu}

Dokážeme, že ak za $p$ zvolíme náhodné prvočíslo z určitého rozsahu,
priemerná hodnota $f$ bude pre ľubovoľné $P$ a $T$ malá. Na zvolenie
náhodného prvočísla môžeme použiť algoritmy z kryptografie používané
na generovanie kľúčov. 


\begin{veta}
Nech $\sigma=2$ a $nm\ge 29$ a nech $K=nm^2$. Ak $p$ je náhodné
prvočíslo menšie ako $K$, pravdepodobnosť aspoň jednej falošnej zhody je 
najviac $2,52/m$ a priemerný čas Rabin-Karpovho algoritmu je $O(n+mk)$.
\end{veta}

\paragraph{Dôkaz (nebrali sme, iba pre informáciu)}
Najskôr dokážme, že ak pravdepodobnosť aspoň jednej falošnej zhody 
je najviac $2,52/m$, stredná hodnota počtu zhôd $f$ bude $O(n/m)$ a teda 
do časovej zložitosti prispeje členom $O(n)$:
$$E(f)=\sum_{i=0}^{n-m+1}i \cdot P(f=i) \leq n \cdot P(f>0) = 2,52 \cdot {n \over m}$$

Označme $\pi(n)$ počet prvočísel menších alebo rovných $n$. V dôkaze použijeme
nasledjúce vlastnosti prvočísel:
\begin{enumerate}
    \item ${n \over \ln(n)} \leq \pi(n) \leq 1,26 \cdot {n \over \ln(n)}$
    \item pre $n \geq 29 $ súčet prvočísel $\leq n $ je $\geq 2^n$
    \item $n \geq 29$ tak každé $k \leq n2^n$ je deliteľné najviac 
          $\pi(n)$ prvočíslami
\end{enumerate}
Nech $\alpha_i = P - T[i..i+m-1]$. Keďže nepočítame modulo $p$, platí, že
 $\alpha_i=0 \Leftrightarrow$ výskyt na pozícii $i$. Súčasne $\alpha_i<2^i$.
$$S(P,T) = \prod_{i: \alpha_i \neq 0} \alpha_i \leq 2^{mn}$$
Preto $S(P,T)$ má najviac $\pi(mn)$ prvočíselných deliteľov.
Vzorka má falošný výskyt v texte práve vtedy, keď $\alpha_i$ je deliteľné prvočíslom $p$. Z $\pi(K)$ prvočísel najviac $\pi(mn)$ má falošnú zhodu (t.j. delí $S(P,T)$).

$$P(f>0) \leq {\pi(m.n)\over \pi(K)}\leq 1,26 \cdot {n.m.\log(n.m^2) \over n.m^2.\log(n.m)} \leq {2.52 \over m}$$
QED

Namiesto jedného prvočísla môžeme použiť aj $L$ nezávislých prvočísel $p_1, p_2,\dots,p_L$. Nech  $f_{p,i}$ nám označuje udalosť, že náhodne zvolené prvočíslo $p$ má falošnú zhodu na pozícii $i$. Falošná zhoda v tomto rozšírenom algoritme nastane ak pre nejaké $i$ majú všetky zvolené prvočísla $f_{p,i}=1$, t.j. pravdepodobnosť, že toto nastane je $P(\exists i \forall j f_{p_j,i})$. 

\paragraph{Odhad 1}
\begin{eqnarray*}
P(\exists i \forall j f_{p_{j,i}}) 
 &\leq& P(\forall j \exists i f_{p_{j,i}})\\
 &=& \prod_j P(\exists i f_{p_{j,i}})\\
 &\leq& ({\pi(m.n) \over \pi(k)})^L
\end{eqnarray*}

\paragraph{Odhad 2}
Budeme vychádzať z poznatku, že $\alpha_i < 2^m$ a teda najviac $\pi(m)$ prvočísel môže deliť $\alpha_i$. Teda pre dané $i$ a náhodné $p$ máme $P(f_{p.i})\le \pi(m)/\pi(K)$.
$$P(\exists i \forall j f_{p_{j,i}}) \leq n \cdot P(\forall j f_{p_{j,i}}) = n\cdot P(f_{p_{j,i}})^L \leq n \cdot ({\pi(m) \over \pi(k)})^L$$

\paragraph{Príklad} Nech $m = 1000$ a $n = 100\,000$, potom $K = nm^2 = 10^{11} \sim 2^{36}$. Pre $L = 4$ dokázané odhady na pravdepodobnosť falošnej zhody vyzerajú nasledovne:
\begin{itemize}
\item pre 1 prvočíslo: $2,52 . 10^{-3}$
\item odhad $1$ pre $L$ prvočísel: $4 . 10^{-11}$
\item odhad $2$ pre $L$ prvočísel: $5 . 10^{-21}$
\end{itemize}

\section{Využitie bitového paralelizmu}

\subsection{Shift-and algoritmus}
%B. D¨om¨olki: An algorithm for syntactic analysis. Computational Linguistics, 8 1964, pp. 29 - 46.
%canot find at http://www.mt-archive.info/MechTrans-TOC.htm
%mech transl is predecessor of comput. ling.

%Domolki B  An algorithm for syntactic analysis Computational Linguistics
%3 29-46 1964 (Hungarian journal?).

%Wegner P The Domolki Algorithm s TR 68-18, Department of Computer Science,
%Cornell University May 1968.

%Domolki, B., Algorithms for the recognition of properties of sequences of symbols. Zhurnal
%Vychislitel'noi Matematiki i matematicheskoi Fiziki 5, I (1965), 77-97, translation:
%USSR Computational & Mathematical Physics 5(1) Pergamon Press, Oxford, 1965, 101-130.
%pod menom Domelki

%Domolki's algorithm applied to generalized overlap resolvable grammars
%Wise STOC 1971

%% @article{135243,
%%  author = {Baeza-Yates, Ricardo and Gonnet, Gaston H.},
%%  title = {A new approach to text searching},
%%  journal = {Commun. ACM},
%%  volume = {35},
%%  number = {10},
%%  year = {1992}, 
%%  issn = {0001-0782},
%%  pages = {74--82},
%%  doi = {http://doi.acm.org/10.1145/135239.135243},
%%  publisher = {ACM},
%%  address = {New York, NY, USA},
%%  }
%% verzia z 89?


Algoritmus bol publikovaný v roku 1992 Ricardom Baeza-Yatesom a
Gastonom Gonnetom, avšak podobný algoritmus vynašiel vraj aj Balint Dömölki už 
v roku 1964. Algoritmus funguje pre krátke vzorky, ktorých dĺžka je menšia ako počet bitov jedného registra.  
Majme bitovú maticu $M$ s riadkami
$0,\dots,m-1$ a stĺpcami $0,\dots,n-1$, ktorá je definovaná
nasledovne:
$$M(i,j) = 1 \Leftrightarrow P[0 \dots i] = T[j-i\dots j]$$
V $j$-tom stĺpci si teda pamätáme stavy NKA z Morris-Prattovho
algoritmu, ktoré sú dosiahnuteľné po načítaní $T[0..j]$
(t.j. všetky sufixy $T[0..j]$, ktoré sú prefixami $P$).
Každý stĺpec vieme spočítať z predchádzajúceho podľa vzťahu
$$M(i,j) = (i=0\vee M(i-1,j-1)) \wedge P[i] = T[j]$$
pre $i\ge 0, j>0$.

Pre každé $x \in \Sigma$, nech $U(x)$ je binárny vektor 
dĺžky $m$, taký že $U(x)[i]=1 \Leftrightarrow P[i] = x$.

Jednotlivé stĺpce matice $M$ a vektory $U(x)$ si budeme pamätať ako
binárne čísla a robiť s nimi bitové operácie.

Napríklad pre $P=$aaba dostávame čísla $U(a)=1011_2$, $U(b)= 0100_2$.
Pozor, najľavejší znak $P$ je vo vektoroch reprezentovaný 
vpravo, na pozícii najmenej významného bitu.

Dostávame takto nový vzťah pre výpočet $j$-teho stĺpca $M$ z $j-1$:
$$M(\cdot,j)=((M(\cdot,j-1)<<1|1) \& U(T[j])$$
Tu využívame vzťah 
$P[i] = T[j] \Leftrightarrow U(T[j])[i] = 1$.

Ak $m$ je menej ako dĺžka registra, 
časová zložitosť je $\Theta(n+m+\sigma)$ operácií s registrami.

\subsection{BNDM: Backward non-deterministic DAWG matching}

Je to algoritmus na hľadanie jednej vzorky v texte. Používa bitový
paralelizmus, preto je vhodný pre krátke vzorky. Publikovali ho 
Navarro a Raffinot v roku 1998.

%NAVARRO G., RAFFINOT M., 1998. 
%A Bit-Parallel Approach to Suffix Automata: FastExtended String Matching, CPM

V každom kroku, keď máme zarovnanú vzorku na nejaké okno textu s
posunom $i$, hľadáme najdlhšie $\alpha$, ktoré je (vlastným) sufixom tohto
okna a prefixom $P$. Potom posunieme okno tak, aby nájdené
$\alpha$ boli zarovnané. Ako ale nájdeme $\alpha$? Ideme premennou $j$
postupne od konca okna, v každom kroku pridáme na začiatok $\alpha$
jeden znak. V každom kroku udržujeme všetky výskyty 
aktuálneho sufixu $\alpha$ v 
$P$ --- to sú kandidáti na najdlhší možný prefix $P$. 
Udržujeme si ich pomocou
bitového vektora $B$, v ktorom je jednotka na začiatočnej
pozícii každého výskytu $\alpha$.

\includegraphics[width=80mm]{figures/l05-bndm.eps}

\begin{lstlisting}
i=0;
while(i<=n-m){
  j = m-1;
  last_j = m-1;
  B = (1<<m)-1;  //m krat 1
  while(B>0 && j>=0){
    B = (B >> 1) & U[T[i+j]];
    if(B & 1){  // vyskyt podslova na zaciatku P?
      if(j==0) print i;  // vyskyt podslova dlzky m?
      else last_j = j;  // posunme posledny najdeny prefix
    }
    j--;
  }
  i += last_j;  //posunme sa na posledny najdeny prefix
}
\end{lstlisting}

Pole $U$ obsahuje pre každý znak jeden bitový reťazec, ktorý má
jednotky na výskytoch vo vzorke, podobne ako v Shift-and algoritme.
To sa predpočíta v $O(m)$ jedným prejdením vzorky s tým, že ešte pole
v čase $O(\sigma)$ inicializujeme na nuly.

Najhorší prípad je $O(mn+\sigma)$.
Priemerný prípad $O(n\frac{\log_\sigma m}{m}+m+\sigma)$.



\section{Prehľad algoritmov}
V tabuľke \ref{tab:time_table} uvádzame prehľad všetkých preberaných algoritmov na hľadanie vzorky v texte.

\begin{table}
	\centering
	\begin{tabular}{|l|l|l|l|l|}
\hline
Algoritmus & najhorší prípad	& priemerný prípad	& porovnávanie	& Poznámka \\
\hline
triviálny  & $O(nm)$     & $O(n + m)$   & áno	&  jednoduchý \\%
Gusfield  & $O(n + m)$     & $O(n + m)$   & áno	& zákl. predspracovanie\\%
DKA  & $O(n + \sigma m)$     & $O(n + \sigma m)$   & nie	&   real time\\%
(K)MP  & $O(n + m)$     & $O(n + m)$   & áno	&   \\%
Aho Corasick  & $O((n+m)\sigma + k)$     & $O((n+m)\sigma + k)$   & áno/nie	& viac vzoriek   \\%
Boyer Moore  & $O(nm), O(n + m)$     & $O({n \over \sigma} + m)$   & nie	&   \\%
Shift-and  & $O(n+m+\sigma)$     & $O(n + m + \sigma)$   & nie	&   pre $m$ bitov v registri\\%
BNDM  & $O(nm+\sigma)$     & $O(n \frac{\log_\sigma m}{m} + m + \sigma)$   & nie	&   pre $m$ bitov v registri\\%
Rabin-Karp  & $O(nm)$     & $O(n + mk)$   & nie	&   randomizovaný\\%
\hline
	\end{tabular}
	\caption{Prehľad prezentovaných algoritmov}
	\label{tab:time_table}
\end{table}

\section{Dolný odhad zložitosti vyhľadávania vzorky v texte porovnávaním}

Uvažujme algoritmy, ktoré pristupujú k vzorke a textu len pomocou
porovnaní znakov na rovnosť. Takýmto algoritmom je napríklad KMP,
ale BM ním nie je, kvôli pravidlu zlého znaku.

Chceme dolný odhad počtu porovnaní, ktoré každý takýto
algoritmus musí v najhoršom prípade urobiť. Majme vzorku $P = a^m$ a
zatiaľ nešpecifikovaný text $T$ dĺžky $n$ nad abecedou $\{a,b\}$. Na
tomto vstupe budeme simulovať algoritmus a na každé porovnanie na
rovnosť odpovieme áno. Súčasne si zostavíme graf, v ktorom vrcholy
budú jednotlivé znaky textu $T$ a jeden vrchol pre celý reťazec $P$.
Máme teda $n+1$ vrcholov.

Každá otázka spojí dva vrcholy, na ktoré sme sa pýtali,
hranou. Po menej ako $n$ otázkach nám zostanú aspoň dva komponenty
súvislosti. Ak teda algoritmus spraví menej ako
$n$ porovnaní, vieme zostrojiť dva reťazce $T$, ktoré sedia so
všetkými otázkami, ale dávajú rôzne odpovede, takže aspoň na jeden z
nich by algoritmus zle odpovedal. Jeden z nich je $T=a^n$ a v druhom
dáme $a$ na všetky pozície, ktoré sú v tom istom komponente ako $P$
a na zvyšné pozície dáme $b$.

\begin{veta}
Každý algoritmus, ktorý pristupuje k reťazcom $P$ a $T$ len pomocou
porovnaní na rovnosť pre každé $n$ a $m<n$ potrebuje v najhoršom aspoň 
$n$ porovnaní a pracuje teda v čase $\Omega(n)$.
\end{veta}

Cole a kol. 1995 pre vzorku $P = aba$ dokázali lepší dolný odhad 
${6 \over 5}n - o(n)$.

\section{Hľadanie vzorky v komprimovanom texte}
%autor poznamok: B.Brejova

Pri veľkých súboroch ich chceme držať v komprimovanom stave a
vyhľadávať v nich vzorku bez toho, aby ich bolo nutné dekomprimovať.
Ako $n$ teraz označíme veľkosť komprimovaného vstupu, $u$
  nekomprimovaného, chceme pokiaľ možno byť nezávislý od $u$, ideálne
  $O(n+m)$. Dĺžka vzorky $m$ sa meria v nekomprimovanom stave.

\subsection{Run length encoding, RLE}

\begin{itemize}

\item Zapíš $k$ po sebe idúcich kópií znaku
  $a$ ako $a^k$. Dobré kódovanie napr. na binárne bitmapy, často
  väčšie oblasti bielej alebo čiernej. Text komprimovanej dĺžky $n$ má
  teda tvar $t_1^{k_1},\dots ,t_n^{k_n}$, kde $k_i\ge 1$ a $t_i\ne
  t_{i+1}$. Nezaujíma nás teraz počet bitov textu, ale počet run-ov.

\item Jednoduchá idea vyhľadávania: 
považujeme $a^k$ za znak $(a,k)$ v špeciálnej
  abecede (nekonečnej veľkosti), zakódujeme tak aj vzorku a použime
  KMP algoritmus.


\item Problém so začiatkom a koncom vzorky. Nech vzorka začína v RLE
  znakom $(a,k)$ a končí $(b,\ell)$, pričom predpokladajme, že $a\ne
  b$. Potom vo vzorke aj texte všetky znaky $(a,j)$ pre $j>k$
  nahradíme dvojicou znakov $(a,j-k)(a,k)$ a podobne znaky $(b,j)$ pre
  $j>\ell$ nahradíme dvojicou $(b,\ell)(b,j-\ell)$. Teraz už môžeme 
  naozaj použiť KMP algoritmus.

\item Cvičenie: čo so vzorkami, ktoré začínajú aj končia na rovnaké
  písmeno?

\item Zložitosť $O(n+m)$, komprimovaný text môže čítať a spracovávať
  po znakoch. Zložitosť zostáva $O(n+m)$ dokonca aj ak $m$ by bola
  komprimovaná dĺžka vzorky.

\end{itemize}

\subsection{LZW kompresia (Lempel–Ziv–Welch 1984)}

Používaná vo formáte GIF, v minulosti populárna na UNIXe, ale mala aj
problémy kvôli patentovanému algoritmu.

Algoritmus kompresie číta text a postupne buduje lexikografický strom.
Vrcholy stromu sú číslované. Na začiatku zostavíme strom, v ktorom
koreň má číslo 0 a list pre každý znak abecedy s číslami $1\dots
\sigma$.  Predpokladajme teraz, že sme už zakódovali určitú časť textu
a vytvorili tým nejaký väčší strom. Podľa začiatku doteraz nezakóvaého
textu algoritmus pokračuje po strome kým sa dá, potom do
komprimovaného súboru vypíše číslo vrchola, v ktorom skončil. Pozrie
sa na ďalšie písmeno textu a pridá ho ako dieťa aktuálneho vrcholu
(toto písmeno však zatiaľ zostáva nekomprimované). Potom sa vráti do
koreňa a opakuje. Príklad sa nachádza na obrázku
\ref{fig:l05-lzw}. Ako $n$ budeme označovať počet vypísaných čísel
vrcholov.

\begin{figure}
\begin{minipage}[t]{0.3\textwidth}
~\\[-\baselineskip]
\includegraphics[width=\textwidth]{figures/l05-lzw.eps}
\end{minipage}
\hfill
\begin{minipage}[t]{0.69\textwidth}
Text: aabbaabbabcccccc\\
Komprimovaný text: 1, 1, 2, 2, 4, 6, 5, 3, 11, 12
\end{minipage}
\caption{Príklad LZW kompresie a vzniknutého lexikografického stromu} 
\label{fig:l05-lzw}
\end{figure}

Cvičenie: aký dlhý bude zápis pre $a^n$?

Dekompresia: vytvárame ten istý strom, ako pri kompresii. Nech
komprimovaný text je $z_0,\dots, z_{n-1}$. Na začiatku začneme strom s
prvkami abecedy. Po prečítaní čísla vrchola $z_i$ zo vstupu vypíšeme
reťazec pre tento vrchol stromu. Pozrieme sa na ďalšie číslo $z_{i+1}$
zo vstupu a prvý znak z reťazca pre tento vrchol stromu pridáme ako
nový vrchol pod vrchol $z_i$. Môže sa ale stať, že vrchol $z_{i+1}$
ešte v strome nie je, práve ho ideme pridať. Vtedy použijeme prvý znak
slova pre vrchol $z_i$, ktorý bude súčasne aj prvým znakom pre
$z_{i+1}$.  Ak by sme chceli tento strom iba vytvárať a nevypisovať
dekomprimovaný text, dá sa to v čase $O(n)$ (v každom vrchole si
potrebujeme pamätať aj prvé písmeno slova pre tento text).

Na vyhľadávanie vzorky v komprimovanom texte si ukážeme ideu algoritmu
od autorov Amir, Benson, Farach 1994, ktorý funguje v čase $O(n+m^2)$,
aj keď v našej verzii skôr $O(n+m^3)$. Navyše budeme hľadať iba prvý
výskyt vzorky. Predpokladáme konštantnú abecedu a budeme simulovať, čo
by robil deterministický konečný automat na dekomprimovanom texte, ale
chceme vždy v konštantom čase spracovať celý úsek textu reprezentovaný
jedným číslom vrchola zo vstupu. Po načítaní čísla vrchola $z_q$ chceme
v konštantnom stave zistiť, v akom stave bude DKA na konci textu
reprezentovanom týmto vrcholom. Pripomeňme si, že tento stav zodpovedá
najdlhšiemu sufixu textu, ktorý je prefixom vzorky $P$. Sú dva
prípady:

\begin{itemize}
\item Tento sufix je celý vo vnútri reťazca reprezentovaného vrcholom
  $z_q$. Pre každý vrchol lexikografického stromu teda chceme vedieť,
  aký najdlhší sufix jeho slova je prefixom vzorky. Túto hodnotu si
  budem ukladať priamo vo vrchole a spočítame ju ľahko pri vytváraní
  vrcholu aplikovaním jedného kroku DKA na stav v jeho rodičovi.

\item Tento sufix obsahuje celý reťazec reprezentovaný vrcholom $z_q$ a
  navyše zasahuje aj do textu reprezentovaného $z_0\dots z_{q-1}$. 
  To znamená, že vrchol $z_q$ reprezentuje nejaký
  podreťazec $P[j..k]$ vzorky $P$. Takých vrcholov je v strome $O(m^2)$. Nech
  stav DKA po prečítaní $z_{q-1}$ bol $i$, teda zodpovedá prefixu
  $P[0..i-1]$. Predpočítame si vopred tabuľku veľkosti $O(m^3)$, ktorá
  pre každé $i$, $j$ a $k$ vráti najdlhší sufix v $P[0..i-1]P[j..k]$,
  ktorý je prefixom $P$. Indexy $j$ a $k$ budeme mať uložené vo
  vrchole a spočítame ich hoci aj triviálnym vyhľadávaním v $P$,
  ale len pre vrcholy, kde rodič bol podreťazcom $P$.
\end{itemize}

Ak po niektorom čísle dostaneme hodnotu stavu $m$, našli sme
výskyt. Môže sa však stať, že DKA by nadobudol stav $m$ niekde
uprostred úseku reprezentovaného jedným číslom a výpočet týchto stavov
sme preskočili. Prvý výskyt vzorky nikdy nebude celý vo vnútri úseku
reprezentovaného jedným číslom, lebo to číslo zodpovedá reťazcu, ktorý
sme už museli predtým nájsť v texte. Teda $P[i..m-1]$ bude na začiatku
úseku kódovaného číslom $z_q$ a $P[0..i-1]$ bude v predchádzajúcich
úsekoch.  Pritom stav po prečítaní $z_{q-1}$ musí byť nejaké $j\ge i$.
Pre každý vrchol reprezentujúci slovo $u$ si pamätáme aj dĺžku
najdlhšieho prefixu $u$, ktorý je sufixom vzorky. Toto si tiež
skopírujeme z rodiča a zmeníme len ak celé $u$ je sufixom, čo sa stane
iba $m$ krát v niektorých z $O(m^2)$ vrcholoch, ktoré sú podslovami
$P$. Ak teda cez hranicu medzi $z_{q-1}$ a $z_q$ ide výskyt vzorky,
musí sa nachádzať vo vnútri $P[0..i-1]P[k..m-1]$. Pre každé $i$ a $k$
si predpočítame, či tento reťazec vzorku obsahuje a ak áno, tak kde.
