\section{Boyerov-Moorov algoritmus}

Boyerov-Moorov (BM) algoritmus (1977) kontroluje vzorku odzadu a občas vie
niektoré časti textu úplne preskočiť. Preto je v praxi často o niečo
rýchlejší ako KMP algoritmus.  Ako takmer pri každom algoritme na
spracovanie textu najskôr vzorku predspracuje a potom ju vyhľadáva
v texte. Podobá sa na triviálny algoritmus s kontrolou odzadu:
\begin{lstlisting}
i=0;
while(i<=n-m){
  j=m-1;
  while(j>=0 && P[j]==T[i+j]){
    j--;
  }
  if(j<0){ print i; }
  i+=skip;
}
\end{lstlisting}

Ak ${\rm skip}=1$, máme štandardný triviálny algoritmus (akurát
porovnávame vzorky odzadu). Ak však zoberieme text $T=bbbbbb$ a vzorku $P=baa$,
tak by sme mohli v obidvoch krokoch nastaviť ${\rm skip}$ na $2$ (pozri obr. \ref{fig:priklad}). 
Pre všeobecnú vzorku a
všeobecný text si nemôžeme dovoliť vždy skákať o $2$.  Namiesto toho BM
algoritmus skáče podľa potreby. Presnejšie podľa nasledovných dvoch pravidiel
(skáče podľa toho, ktoré pravidlo povie viac):

\begin{figure}
\begin{verbatim}
bbbbbbb   <-text
  # # #   <-porovnania
baa       <-vyskúšané posuny vzorky
  baa
    baa 
\end{verbatim}
\caption{Ak porovnávame vzorku $P=baa$ s textom $T=bbbbbb$, môžeme
  vždy posunúť vzorku o dve, aby sa jediný výskyt 'b' vo vzorke dostal
  oproti práve nájdenému 'b' v texte. Celkovo sa pozrieme iba na 3 zo 7 znakov textu.}
\label{fig:priklad}
\end{figure}

\begin{itemize}
	\item Pravidlo zlého znaku (bad character rule)
	\item Pravidlo dobrého sufixu (good suffix rule)
\end{itemize}

\subsection{Pravidlo zlého znaku}

Nech $R[x]$ je index posledného (najpravejšieho) výskytu písmena $x\in \Sigma$
vo vzorke $P$, alebo $-1$, ak $x$ vo vzorke $P$ neexistuje. $R[x]$ vypočítame
nasledovným algoritmom:

\begin{lstlisting}
R={-1,-1,-1,...}
for(i=0; i<m; i++) {
   R[P[i]]=i;
}
\end{lstlisting}


Táto časť trvá $O(m+\Sigma)$ a potrebujeme si pamätať pole o veľkosti
$O(\Sigma)$.

\begin{figure}
\begin{center}
\begin{verbatim}
                 i    
T  .......................xabcd.......
P                ....x....yabcd
P                     ....x....yabcd
                          j
\end{verbatim}
\end{center}
\caption{Na pozícii $j$ nastala nezhoda a preto môžeme vzorku posunúť na
najbližšie $x$.}\label{poz3figure4}
\end{figure}

\paragraph{Pravidlo zlého znaku:} 
Ak $P[j+1..m-1]=T[i+j+1..i+m-1]$ a $P[j]\ne T[i+j] = x$ a
$R[x]<j$, tak spravíme posun o $j-R[x]$. Ak $R[x]>j$,
t.j. posledný výskyt $x$ je až za súčasnou pozíciou $j$, posunieme sa
o jedna. Pravidlo zlého znaku je ilustrované na obrázku
\ref{poz3figure4}.

Pri malých abecedách často dôjde iba k malým posunom, 
pri veľmi veľkých treba veľa času a pamäte na pole $R$,
ale pri stredne veľkých je to dobrá heuristika.

\subsection{Horspoolov algoritmus} 

Variant BM, ktorý nevyužíva pravidlo dobrého sufixu, iba 
mierne modifikované pravidlo zlého znaku.
Na rozdiel od BM toto pravidlo neuplatňuje na znak, kde nastala
nezhoda, ale vždy na najpravejší znak aktuálneho okna v texte, 
teda na znak $x=T[i+m-1]$.  
V poli $R$ uložíme posledný výskyt každého znaku v
$P[0..m-2]$, neuvažujeme teda posledný znak vzorky. 
Takto dostávame nasledujúci jednoduchý pseudokód:

\begin{lstlisting}
  R={-1, -1, -1, ...}
  
  for(i=0; i<m-1; i++){
    R[P[i]]=i;
  }

  i=0;
  while(i <= n-m){
    j=m-1;
    while(j>=0 && P[j]==T[i+j]){
      j--;
    }
    if(j<0){ print i; }
    i += m-1-R[T[i+m-1]];
  }
\end{lstlisting}

V priemernom prípade algoritmus pracuje v čase 
$O(n/\sigma+m+\sigma)$, v najhoršom $O(mn+\sigma)$.
Existuje aj (úplne iný) algoritmus 
s priemerným prípadom $O(n\frac{log_{\sigma}m}{m}+m)$ (Lecroq 1992).

\subsection{Pravidlo dobréhu sufixu}

Ak sme v niektorej iterácii našli zhodu medzi $k$ poslednými znakmi
$P$ a príslušnou časťou $T$, chceme $P$ posunúť tak, aby písmená z
$P$, ktoré budú zarovnané s týmito $k$ znakmi, boli tiež zhodné
(pozri obrázok \ref{poz3figure7}).

\begin{figure}
\begin{center}
\begin{verbatim}
T:  ...............xabcdefg...............
P:            efg..yabcdefg
P:                      efg..yabcdefg
\end{verbatim}
\end{center}
\caption{Príklad pravidla dobrého sufixu.}\label{poz3figure7}
\end{figure}

Budeme písať $P\sim Q$ práve vtedy, keď $P$ je sufix $Q$ alebo $Q$ je
sufix $P$.  Ak nájdeme prvú nezhodu na pozícii $j$ v $P$, posunieme $i$ o
$\gamma[j]$ definované takto:
$$\gamma[j]=m-\max\{k\,|\,0\leq k< m \wedge P[j+1..m-1]\sim P[0..k-1]\}.$$
Pozrime sa, čo sa stane v dvoch extrémnych prípadoch algoritmu.
Ak sa v danej iterácii nenašla žiadna zhoda medzi $P$ a časťou 
$T$, premenná $j$ bude mať hodnotu $m-1$, t.j. $P[j+1..m-1]=\varepsilon$.
Pre ľubovoľný reťazec $Q$ platí, že $Q\sim \varepsilon$ a teda $k$ nadobudne
hodnotu $m-1$, čiže posun bude 1. Naopak, ak nájdeme výskyt vzorky,
máme $j=-1$ a teda $P[j+1..m-1]=P$. Hľadáme teda najdlhší vlastný prefix
$P$, ktorý je aj sufixom $P$. Môže sa stať aj to, že jediný takýto
prefix je $\varepsilon$; v tom prípade bude posun $m$.

Hodnoty $\gamma[-1\dots m-1]$ si potrebujeme predspracovať, použijeme
na to pole $sp$ z Morris-Prattovho algoritmu. Hodnota $sp[i]$ je dĺžka
najdlhšieho vlastného sufixu $P[0..i-1]$, ktorý je prefixom $P$.
Použijeme aj pole $spr$, ktoré spočítame ako pole $sp$ pre $P^R$, čo
je zrkadlový obraz reťazca $P$. Hodnota $spr[i]$ je dĺžka najdlhšieho
vlastného prefixu $P[m-i..m-1]$, ktorý je sufixom $P$. 

Pri výpočte $\gamma[j]$ môžu nastať dve situácie. Prvá je, že
$X=P[j+1..m-1]$ vyskytuje v $P$ ešte raz a z týchto výskytov $X$ chceme
spočítať pravý koniec toho najpravejšieho. Pre každý výskyt $X$
začínajúci na nejakej pozícii $m-i$ platí, že $spr[i]\ge m-j-1$
a navyše pre najpravejší výskyt platí rovnosť $spr[i]= m-j-1$,
lebo pri nerovnosti máme zaručený ešte jeden výskyt viac v pravo, na
začiatku sufixu $P$ dĺžky $spr[i]$. Naopak, ak $spr[i]= m-j-1$,
na pozícii $m-i$ začína výskyt $X$. Takže hľadáme najmenšie $i$, pre
ktoré platí rovnosť $spr[i]= m-j-1$. Ak $X$ začína na pozícii 
$m-i$, končiť bude na pozícii $(m-i)+spr[i]-1$, teda za $\gamma[j]$
použijeme $m-(m-i)-spr[i]=i-spr[i]$.

Druhá možná situácia je, že $X$ nemá ďalšiu kópiu v $P$. Hľadáme teda
najdlhší sufix $P[j+1..m]$, ktorý je prefixom $P$ a nakoľko celé $X$
sa druhýkrát nevyskytuje, dĺžka tohto sufixu je $sp[m]$.  V
nasledujúcom kóde najskôr vypočítame $\gamma$ podľa tohto pravidla,
potom prepisujeme podľa výskytov $X$ ktoré hľadáme zľava (t.j. od
najväčších hodnôt $i$).

\begin{lstlisting}
compute sp;
compute spr;
for(j=-1; j<m; j++) {
  gamma[j] = m-sp[m];
}
for(i=m; i>=0; i--) {
  j = m-spr[i]-1;
  gamma[j] = i-spr[i];
}
\end{lstlisting}

Ak zoberieme vzorku $P=a^m$ a text $T=a^n$, tak nájdenie všetkých výskytov bude až kvadratické. Dokonca je možné spraviť takú vzorku a text, že vzorka sa v texte nebude nachádzať, ale napriek tomu bude čas behu BM algoritmu kvadratický.
Kvôli tomu bolo spravené silné pravidlo dobrého sufixu, ktoré tento problém
čiastočne vyrieši. Ak sa vzorka v texte nenachádza, časová zložitosť je $O(n+m)$. Silné pravidlo dobrého sufixu je ilustrované na obrázku \ref{poz3figure8}.

\begin{figure}
\begin{center}
\begin{verbatim}
T: ....................xabcd..............
P:   ..zabcd..yabcd....yabcd
P:                   ..zabcd..yabcd....yabcd
\end{verbatim}
\end{center}
\caption{Silné pravidlo dobrého sufixu: hľadáme posledný výskyt $P[j+1..m]$ v $P$, pred ktorým ide iné písmeno ako $P[j]$.}\label{poz3figure8}
\end{figure}

Galil v roku 1979 spravil zlepšenie, ktoré beží v čase $O(n+m)$ v ľubovoľnom
prípade. Dosiahol to tak, že ak preskočíme kus textu pomocou pravidla dobrého
sufixu (silného), tak vieme, že istý kus v strede vzorky je rovnaký ako text
a preto tam nemusíme porovnávať, čím si ušetríme prácu.
