\section{Triviálny algoritmus pre vyhľadávanie vzorky v texte}

Máme daný reťazec $P$ dĺžky $m$ a reťazec $T$ dĺžky $n$. Úlohou je 
nájsť všetky pozície $\{i_1, i_2,\dots \}$ také, že $T[i_j..i_j+m-1]=P$.

Triviálny algoritmus skúsi každú potenciálnu pozíciu výskytu $i$ a
skontroluje, či $T[i]=P[0]$, $T[i+1]=P[1]$, \dots, $T[i+m]=P[m]$.
Ak áno, $i$ je ďalšia pozícia výskytu. Pozície stačí skúšať po
$n-m$, inak by sa nám $P$ do $T$ nezmestilo.

\begin{lstlisting}
for(i=0; i<=n-m; i++) {
  j=0;
  while(j<m && P[j]==T[i+j]) { // (*)
    j++;
  }
  if(j==m) {
    print(i);
  }    
}
\end{lstlisting}

\paragraph{Časová zložitosť v najhoršom prípade.}
Celkovú zložitosť zjavne môžeme odhadnúť zhora na $O(nm)$. Je to však
tesný odhad? Celkový čas je úmerný počtu porovnaní medzi znakmi v
riadku označenom hviezdičkou. Napríklad na vstupe 
$P=$''ma '', $T=$''Ema ma mamu'' potrebujeme $15$ porovnaní.
V najhoršom prípade tento algoritmus
potrebuje $m(n-m+1)$ porovnaní. Uvažujme napríklad reťazce
$P=a^m$, $T=a^n$. Pre každé $i$ porovnáme všetky znaky $P$.


V klasickej zložitosti uvažujeme čas ako funkciu celkovej dĺžky vstupu
$N=m+n$. Aká je zložitosť tohto algoritmu v najhoršom prípade? Z
hornej hranice $O(mn)$ dostávame triviálne $O(N^2)$. Ak nastavíme
$m=N/4$ a $n=3N/4$, dostávame, že hore-uvedený vstup vyžaduje $N/4
(N/2+1)$ porovnaní, takže zložitosť v najhoršom prípade je $\Theta(N^2)$.
Pri niektorých aplikáciách sa spracovávajú veľmi veľké texty a prípadne
aj veľké vzorky, takže takáto zložitosť nepostačuje.

Všimnite si však, že okrem pamäte potrebnej na uloženie $P$ a $T$
algoritmus potrebuje iba konštantnú ďalšiu pamäť. Tiež čas a pamäť
nezávisia od veľkosti abecedy (za predpokladu, že jednotlivé znaky sa
zmestia do jedného registra).

%novy odstavec 
Na mnohých vstupoch sa však tento algoritmus nespráva
až tak zle. Napríklad, ak sa prvé písmeno vzorky $P[0]$ nevyskytuje v
texte $T$, urobíme iba $n-m+1$ porovnaní. Prípady, kde je počet
porovnaní veľký, majú veľa opakujúcich sa znakov alebo ich skupín.  Ak
napríklad platí, že $P[0]$ sa nevyskytuje vo zvyšku vzorky, počet
porovnaní bude lineárny, čo si dokážeme technikou, ktorá sa volá
amortizovaná analýza zložitosti. Amortizovaná analýza sa používa
vtedy, ak niektoré iterácie algoritmu (alebo niektoré operácie na
dátovej štruktúre), trvajú dlho a iné krátko a chceme dokázať, že v
najhoršom prípade bude súčet týchto krátkych a dlhých operácií pomerne
malý.  V našom prípade chceme nájsť horný odhad počtu porovnaní
znakov, pričom predpokladáme, že $P[0]$ sa nevyskytuje vo zvyšku
vzorky, ale inak môžu byť vzorka aj text ľubovoľné. Ak sa pri
porovnávaní vzorky na pozícii $i$ spraví $k>1$ porovnaní, znamená to,
že $P[1..k-2] = T[i+1..i+k-2]$ a teda v $T[i+1..i+k-2]$ sa nevyskytuje
znak $P[0]$.  V každej z ďalších $k-2$ iterácií teda spravíme najviac
1 porovnanie.  Máme dva typy iterácií: lacné, v ktorých spravíme
iba 1 porovnanie a drahé, v ktorých spravíme viac
porovnaní. Predstavme si, že každé porovnanie má cenu jedna. Za každý
typ iterácie ``zaplatíme'' do pomyselnej kasičky sumu 2. Pri drahej
iterácii táto suma zaplatí prvé porovnanie znaku $P[0]$ s $T[i]$ a
posledné provnanie, v ktorom sa našla nezhoda. Zhody na pozíciách
$P[1..k-2]$ zostanú zatiaľ nezaplatené. Každá z lacných iterácií
zaplatí svoje jedno porovnanie a splatí jedno porovnanie z dlhu, ktorý
narobila predchádzajúca drahá iterácia. Nakoľko tento dlh bol $k-2$ a
počet lacných iterácií za drahou je tiež aspoň $k-2$, celý dlh
splatia. Za celý prechod algoritmom sa teda splatia všetky
porovnania, možno s výnimkou poslednej drahej iterácie, za ktorou sa
už do reťazca nemusia ``zmestiť'' ďalšie lacné, takže potrebujeme ešte
doplatiť najviac $m-2$. Celkovo teda zaplatíme $2(n-m+1)+m-2\le 2n$, a
toto číslo je horný odhad na počet porovnaní v algoritme. 

\paragraph{Časová zložitosť v priemernom prípade.}
Aký bude priemerný prípad?
Uvažujme binárnu abecedu. Chceme spočítať priemerný čas (resp. počet
porovnaní) cez všetky reťazce $P$ a $T$ dĺžky $n$ a $m$. Nech
$c_i(P,T)$ je počet porovnaní znakov v interácii $i$. Potom
priemerný počet je
\begin{eqnarray*}
&& \frac{1}{2^{n+m}} \sum_{P\in\{0,1\}^m,T\in \{0,1\}^n} 
   \sum_{i=0}^{n-m} c_i(P,T)\\
&=& \frac{1}{2^{n+m}} \sum_{i=0}^{n-m} 2^{n-m} 
    \sum_{P\in\{0,1\}^m,T'\in \{0,1\}^m} c_0(P,T')\\
&=& \frac{n-m+1}{2^{2m}} \sum_{P\in\{0,1\}^m,T'\in \{0,1\}^m} c_0(P,T')
\end{eqnarray*}
Počet dvojíc $P$ a $T$ dĺžky $m$, kde urobíme $j$ porovnaní pre $j<m$ je
$2^j 4^{m-j} = 2^{2m-j}$ (na prvých $j-1$ pozíciách majú ten istý, ale ľubovoľný 
znak a na pozícii $j$ majú opačný znak, zvyšné pozície majú ľubovoľné).
Počet reťazcov, kde spravíme $m$ porovnaní, je  $2^{m-1} 4$. Teda dostávame 
$$\sum_{P\in\{0,1\}^m,T\in \{0,1\}^m} c_0(P,T) = \sum_{j=1}^{m-1} j2^{2m-j} + m2^{m+1}.$$

Celkovo dostávame ako
priemerný počet porovnaní sumu $(n-m+1)(\sum_{j=1}^{m-1}j/2^j +
m/2^{m-1})$. Skúsme odhadnúť jej hlavnú časť (použijeme súčet
geometrickej postupnosti $\sum_{i=0}^n q^i = (1-q^{n+1})/(1-q)$ a konkrétne
pre $q=1/2$ máme $2-1/2^n$):
\begin{eqnarray*}
\sum_{j=1}^{m}j/2^j 
&=& \sum_{j=1}^{m}\sum_{i=1}^j 1/2^j
= \sum_{i=1}^m\sum_{j=i}^{m} 1/2^j\\
&=& \sum_{i=1}^m(\sum_{j=0}^{m} 1/2^j-\sum_{j=0}^{i-1} 1/2^j)\\
&=& \sum_{i=1}^m(2-1/2^m - (2-1/2^{i-1}))\\
&=& \sum_{i=1}^m(1/2^{i-1} - 1/2^m )\\
&=& -m/2^m + \sum_{i=0}^{m-1}(1/2^i)\\
&=& -m/2^m + 2-1/2^{m-1}
\end{eqnarray*}
Celkovo dostávame 
\begin{eqnarray*}
&& (n-m+1)(\sum_{j=1}^{m-1}j/2^j + m/2^{m-1})\\
&=& (n-m+1)(\sum_{j=1}^{m}j/2^j + m/2^m)\\
&=& (n-m+1)(2-1/2^{m-1})\\
&\le& 2(n-m+1)
\end{eqnarray*}
Takže časová zložitosť v priemernom prípade je lineárna.

\paragraph{Odvodenie priemernej zložitosti pomocou pravdepodobnosti.}

O niečo jednoduchšie je odvodiť tento vzťah pomocou pravdepodobnosti.
Predstavme si náhodný proces, v ktorom generujeme jednotlivé znaky vo
vzorke aj v texte nezávisle z rovnomerného rozdelenia na
$\Sigma=\{0,1\}$ (t.j. $m+n$ krát si hodíme mincou a zapíšeme si
výsledok ako binárne reťazce $P$ a $T$). Nech $X$ je náhodná premenná
označujúca počet porovnaní, ak na takto vygenerovaných náhodných
reťazcoch spustíme triviálny algoritmus. Potom priemerný počet
porovnaní, ktorý sme počítali v predchádzajúcich odstavcoch, je rovný 
 strednej hodnote premennej $X$, t.j. $E(X)$. Označme si ešte dve 
sady premenných: nech $X_i$ je počet porovnaní v iterácii $i$
(t.j. keď $P[0]$ zarovnáme s $T[i]$) a nech $Y_i$ je 
dĺžka najdlhšieho spoločného prefixu reťazcov $P$ a $T[i..n-1]$. 

Potom $X=\sum_{i=0}^{n-m} X_i$. Stredná hodnota je lineárna a teda
$E(X) = \sum_{i=0}^{n-m} E(X_i)$. Z definície strednej hodnoty máme
$E(X_i) = \sum_{j=1}^{m} j P(X_i = j)$. Pre $k<m$ máme že $X_i=k$
práve vtedy, keď $Y_i=k-1$, lebo triviálny algoritmus skontroluje celý
spoločný prefix a ešte aj prvý rozdielny znak. Podobne, $X_i=m$ práve
vtedy keď $Y_i\ge m-1$. Môžeme teda písať:

\begin{eqnarray*}
E(X_i) 
&=& \sum_{k=1}^{m} k P(X_i = k) \\
&=& m P(Y_i \ge m-1) + \sum_{k=1}^{m-1} k P(Y_i = k-1)\\
&=& m P(Y_i \ge m-1) + \sum_{k=1}^{m-1} k (P(Y_i \ge k-1)-P(Y_i \ge k))\\
%&=& \sum_{k=1}^{m} k P(Y_i \ge k-1) - \sum_{k=1}^{m-1} kP(Y_i \ge k)\\
%&=& \sum_{k=0}^{m-1} (k+1) P(Y_i \ge k) - \sum_{k=1}^{m-1} kP(Y_i \ge k)\\
%&=& \sum_{k=0}^{m-1} P(Y_i\ge k) \\
\end{eqnarray*}
Keď si súčet rozpíšeme, zistíme, že sčítance pre susedné hodnoty $k$
zdieľajú jednu z pravdepodobností a ich odčítaním sa teda výraz značne
zjednoduší (tzv. teleskopická suma)
\begin{eqnarray*}
E(X_i) 
&=& 1(P(Y_i \ge 0)-P(Y_i \ge 1)) + 2(P(Y_i \ge 1)-P(Y_i \ge 2))
+ 3(P(Y_i \ge 2)-P(Y_i \ge 3))\\
&& \quad + \dots + (m-1)(P(Y_i \ge m-2)-P(Y_i \ge m-1))+ m P(Y_i \ge m-1)\\
&=& \sum_{k=0}^{m-1} P(Y_i\ge k).
\end{eqnarray*}

Aby dĺžka spoločného prefixu $Y_i$ bola aspoň $k$, musí sa prvých $k$ znakov
medzi $P$ a $T[i..n-1]$ zhodovať, pričom každá dvojica sa zhoduje 
s pravdedobnosťou $1/2$ nezávisle od ostatných dvojíc. 
Takže máme $P(Y_i\ge k)= 2^{-k}$. Celkovo teda dostávame
$$E(X_i) =  \sum_{k=0}^{m-1} 2^{-k} = 2-2^{-m+1}$$ a po vynásobení
$(n-m+1)$ pozíciami pre $i$ dostávame pre $E(X)$ rovnaký vzťah ako predtým.

\paragraph{Iné rozdelenie pravdepodobnosti pre reťazce.}

Odvodenie priemernej zložitosti pomocou pravdepodobnosti má aj tú
výhodu, že sa dá ľahko rozšíriť napríklad na prípad, keď 
0 a 1 sa v texte vyskytujú nerovnomerne, t.j. $P(T[i]=1)=P(P[j]=1)=p$,
kde $p> 0.5$. Intuitívne čím vyššie $p$, tým väčšia šanca 
že dva náhodné znaky budú oba 1 a teda sa budú zhodovať.
Pravdepodobnosť, že $P[i]=T[j]$ je $p^2+(1-p)^2$, čo označíme ako $q$.
Aby mali dva reťazce spoločný prefix dĺžky aspoň $k$, musí nastať 
$k$ takýchto nezávislých zhôd za sebou a teda $P(Y_i\ge k)=q^k$.
Podobným postupom ako v prípade $p=1/2$ dostávame
\begin{equation*}
  E(X_{i}) = \sum_{k=0}^{m-1} P(Y_{i}\ge k) = 
\frac{1-q^m}{1-q} = 
\frac{1-(p^{2}+(1-p)^{2})^{m}}{1-p^{2}-(1-p)^{2}}.
\end{equation*}
Na obrázku \ref{obr:l02-graf} vidíme graf $E(X_{i})$ pre $m=100$ ako
funkciu $p$. Pre $p=1/2$ máme v priemere o niečo menej ako dve
porovnania v každej iterácii. So zvyšujúcim sa $p$ rastie šanca
náhodného stretnutia dvoch jednotiek a teda aj priemerný počet
porovnaní. V limite pre $p=1$ dostaneme najhorší prípad, t.j. $m$
porovnaní v každej iterácii.
\begin{figure}
\centerline{\includegraphics{figures/l02-du.eps}}
\caption{\label{obr:l02-graf}Graf $E(X_{i})$ pre $m=100$ ako funkcia $p$.}
\end{figure}

Naopak, ak sú znaky rovnomerne rozdelené z nejakej väčšej abecedy, 
priemerný počet porovnaní klesá, lebo šanca zhody medzi dvoma znakmi
je menšia.

