\section{Najdlhšia spoločná podpostupnosť}

\paragraph{Definícia} \emph{Podpostupnosť} postupnosti $a_1 a_2 \ldots a_n$ je
postupnosť $a_{i_1} a_{i_2} a_{i_3} \ldots a_{i_k}$, kde $1 \leq i_1 < i_2 <
\ldots < i_k \leq n$

\paragraph{Definícia:}
Postupnosť $A$ je spoločná podpostupnosť postupností $S$ a $T$, ak je podpostupnosťou $S$ aj $T$. Dĺžku najdlhšej spoločnej podpostupnosti (longest common subsequence) označujeme $lcs(S, T)$.

\begin{figure}[h]
\begin{verbatim}
S = EMA_MA_MA--MU
T = -MA-MA_MA_EMU
\end{verbatim}
\caption{Najdlhšia spoločná podpostupnosť $S=$ EMA\_MA\_MAMU a $T=$ MAMA\_MA\_EMU je MAMA\_MAMU, teda $lcs(S, T) = 9$.}
\end{figure}

Problém hľadania najdlhšej spoločnej podpostupnosti sa dá redukovať na problém podobnosti reťazcov, ak hodnotiacu funkciu zvolíme nasledovne:
\begin{eqnarray*}
&s(a,a) = 1& \\
&s(a,b) = s(a,-) = s(-,a) = 0&
\end{eqnarray*}
Výsledný algoritmus používa dynamické programovanie a má časovú zložitosť $O(mn)$, pamäťovú zložitosť vieme dosiahnuť $O(m)$. Špecifiká tejto hodnotiacej funkcie využíva nasledujúci algoritmus.

\subsection{Algoritmus Hunt-Szymanski, 1977}

Predstavme si pole $Z[1..m]$, ktoré bude pre každý výskyt písmena v $S$ (na pozícii $i$) obsahovať zoznam indexov $j$ do $T$, pre ktoré platí $T[j] = S[i]$ ("kde v poli $T$ nájdem písmeno $S[i]$"). Utriedený bude od väčších $j$ k menším.
\paragraph{Príklad:}
\begin{eqnarray*}
Z[1] &=& 9 \\
Z[2] &=& 10, 6, 3, 1 \\
Z[3] &=& 7, 4, 2 \\
Z[4] &=& 8, 5 \\
Z[5] &=& 10, 6, 3, 1 \\
&\vdots&
\end{eqnarray*}
Teraz spojíme všetky zoznamy $Z[i]$ do jedného zoznamu $Z$, pričom si pre každé číslo pamätáme z ktorej pozície ktorého $Z[i]$ pochádza (označme si $|Z| = r$):
$$Z = \underline{9,}\:\underline{10,6,3,1,}\:\underline{7,4,2,}\:\underline{8,5,}\:\underline{10,6,3,1,}\dots$$
Ďalej využijeme nasledujúcu lemu.

\paragraph{Definícia:}
Rastúca podpostupnosť postupnosti $Z$ je taká podpostupnosť $Z_{i_1}, Z_{i_2}, \dots, Z_{i_k}$, pre ktorú platí $Z_{i_1} < Z_{i_2} < \dots < Z_{i_k}$. Dĺžku najdlhšej rastúcej podpostupnosti $Z$ (longest increasing subsequence) značíme $lis(Z)$.

\paragraph{Lema:}
$lcs(S,T) = lis(Z)$
\paragraph{Dôkaz} vyplýva zo silnejšieho tvrdenia: medzi rastúcimi podpostupnosťami $Z$ (IS) a spoločnými podpostupnosťami $S$ a $T$ (CS) existuje bijekcia (ktorá zachováva dĺžku). Pre každú IS, ktorá obsahuje $Z[i,j]$ totiž existuje CS, ktorá na danej pozícii obsahuje písmeno $S[i] = T[Z[i,j]]$. A naozaj, z každého zoznamu $Z[i]$ vyberieme najviac jedno číslo (keďže je klesajúci), takže výsledná CS bude podpostupnosť $S$. Navyše daná IS je rastúca postupnosť indexov do $T$, teda výsledná CS bude aj podpostupnosť $T$.

\paragraph{}
Algoritmus teda pozostáva z dvoch krokov:
\begin{enumerate}
	\item konštrukcia $Z$
	\item výpočet $lis(Z)$
\end{enumerate}

\paragraph{Konštrukcia $Z$}
\begin{itemize}
	\item Pre malú abecedu použijeme pole $A[1..\sigma]$, kde $A[c]$ bude zoznam výskytov písmena $c$ v $T$:
\begin{lstlisting}[mathescape=true]
for (i=1; i$\le$n; i++)
  pridaj i na zaciatok A[T[i]]
for (i=1; i$\le$m; i++)
  Z[i] = A[S[i]];
\end{lstlisting}
Časová zložitosť tohoto algoritmu je $O(n+m+\sigma+r)$.
	\item Pre veľkú abecedu uložíme $A$ do hashovacej tabuľky alebo vyhľadávacieho stromu (kľúče budú písmená abecedy, hodnoty budú zoznamy). V druhom prípade budeme mať strom s najviac $m$ prvkami, do ktorého vykonáme $n+m$ prístupov, čo nám dáva časovú zložitosť $O((n+m) \log m + r)$.
	\item Ak za abecedu považujeme riadky vstupných súborov tvorené písmenami z nejakej malej abecedy, potom je výhodné ako dátovú štruktúru pre $A$ zvoliť lexikografický strom (kľúče budú riadky $T$). Časová zložitosť bude $O(n'+m'+r)$, kde $n'$ (resp. $m'$) je súčet dĺžok riadkov v súbore $T$ (resp. $S$).
\end{itemize}

\subsection{Výpočet $lis(Z)$}
Najskôr ukážeme triviálne riešenie pomocou dynamického programovania, ktoré pobeží v čase $O(r^2)$. To neskôr zlepšíme na $O(r \log r)$.

Budeme vypĺňať tabuľku $A[1..r,1..r]$, kde na políčku $A[i,j]$ je najmenšie číslo $x$ také, že $x$ je posledný prvok nejakej rastúcej podpostupnosti dĺžky $j$ postupnosti $Z_1Z_2{\dots}Z_i$ (zoberieme prvých $i$ čísel postupnosti $Z$ a pozrieme sa akým najmenším číslom môže končiť jej rastúca podpostupnosť dĺžky $j$). Okrajové prípady vyriešime $A[i,j] = \infty$ ak taká postupnosť neexistuje a $A[i,0] = -\infty$.

\paragraph{Príklad:}
Zoberme si prvých $9$ čísel postupnosti $Z = 9, 10, 6, 3, 1, 7, 4, 2, 8, \dots$:
\begin{itemize}
	\item pre $j=1$ máme podpostupnosti $(9), (10), (6), \dots, (1), \dots$, teda $A[9,1]=1$
	\item pre $j=2$ máme podpostupnosti $(9,10), (6,7), (6,8), \dots, (1,2), \dots$, teda $A[9,2]=2$
	\item pre $j=3$ končia všetky podpostupnosti $(6,7,8), (3,4,8), \dots$ číslom $8$, teda $A[9,3]=8$
\end{itemize}

Ako teraz $A[i,j]$ vypočítať? Posledný prvok postupnosti reprezentovanej $A[i,j]$ môže byť
\begin{itemize}
	\item $Z_i$, pričom pred ním je rastúca podpostupnosť dĺžky $j-1$ postupnosti $Z_1Z_2{\dots}Z_{i-1}$. $Z_i$ pritom na jej koniec vieme pripojiť len vtedy, ak existuje nejaká postupnosť dĺžky $j-1$, ktorá končí číslom menším ako $Z_i$, čo vieme ľahko zistiť z $A[i-1,j-1]$, kde máme informáciu o postupnosti s najmenším číslom na konci.
	\item $Z_k$ pre nejaké $k<i$. V takom prípade $Z_i$ nevyužijeme a výsledok pre prvých $i-1$ čísel máme v $A[i-1,j]$.
\end{itemize}

\begin{lstlisting}[mathescape=true]
A[0,0] = -$\infty$;
for (i=1; i$\le$r; i++) {
  A[i,0] = -$\infty$;
  A[0,i] = $\infty$;
}
for (i=1; i$\le$r; i++) {
  for (j=1; j$\le$r; j++) {
    if (A[i-1,j-1] < Z_i)
      A[i,j] = min(Z_i, A[i-1,j]);
    else A[i,j] = A[i-1,j];
  }
}
\end{lstlisting}

Z takto vyplnenej tabuľky potrebujeme zistiť najväčšie $k$, pre ktoré existuje $k$-prvková podpostupnosť, teda $lis(Z) = max \{k : A[r,k] < \infty\}$.

\paragraph{}
Poďme teraz zlepšiť časovú zložitosť. Zjavne platí $A[i,j] \le A[i,k]$ pre $j<k$ (ináč by sme postupnosť zodpovedajúcu $A[i,k]$ skrátili o $k-j$ prvkov a dostali lepšiu $j$ prvkovú postupnosť, rovnosť nastane len ak sú obidve hodnoty rovné $\infty$). Z toho vyplýva, že čísla v každom riadku $A$ budú v neklesajúcom poradí. Pozrime sa teraz v koľkých číslach sa budú líšiť dva po sebe idúce riadky. Prvých niekoľko čísel riadku $i-1$ bude menších ako $Z_i$, označme si najvyšší index takéhoto čísla $k$. V prvých $k$ iteráciach cyklu z riadku 7 bude platiť $A[i-1,j] < Z_i$, teda min na riadku 9 vyberie hodnoty z predchádzajúceho riadku tabuľky. V nasledujúcej iterácii už bude platiť $A[i-1,j-1] < Z_i \le A[i-1,j]$, teda do $A[i,j]$ sa priradí hodnota $Z_i$. V ďaľších iteráciach nebude splnená podmienka z 8. riadku, teda budeme len kopírovať hodnoty z predchádzajúceho riadku tabuľky. Z toho vyplýva, že jediná zmena medzi dvomi po sebe idúcimi riadkami bude v $k+1$. stĺpci. Keďže čísla sú v riadkoch utriedené, index $k$ môžeme hľadať binárnym vyhľadávaním.
\begin{lstlisting}[mathescape=true]
A[0] = -$\infty$;
for (i=1; i$\le$r; i++)
  A[i] = $\infty$;
for (i=1; i$\le$r; i++) {
  k = najvacsi index taky, ze A[k] < $Z_i$;
  A[k+1] = $Z_i$;
}
\end{lstlisting}

Tento algoritmus nám teda spočíta dĺžku a posledný prvok najdlhšej rastúcej podpostupnosti. Ak potrebujeme zrekonštruovať celú podpostupnosť, použijeme pomocné pole ukazovateľov na dvojice $B[1..r]$. Prvý člen dvojice bude $Z_i$ pre nejaké $i$, teda prvok podpostupnosti, ktorý patrí na príslušné miesto. Druhý člen bude ukazovateľ na zvyšok postupnosti. Zakaždým po priradení na riadku 6 si do $B[k+1]$ uložíme dvojicu ($Z_i$, kópia ukazovateľa z $B[k]$). Celú podpostupnosť potom máme uloženú ako spájaný zoznam v $B[lis(Z)]$ od posledného prvku.

V druhej fáze algoritmu sme $r$-krát volali binárne vyhľadávanie na $r$ prvkoch. Sčítaním časových zložitostí obidvoch fáz teda dostávame odhad $O((n+m) \log m + r + r \log r)$. Bez ujmy na všeobecnosti budeme predpokladať $n>m$. Ďalej $r$ je počet nejakých dvojíc, kde počet možností pre prvý člen je $n$ a pre druhý člen $m$, teda môžeme použiť ohraničenie $0 \le r \le nm$. Potom platí aj $\log r \le \log n^2 = 2\log n$. Z toho vyplýva odhad časovej zložitosti $O((n+r) \log n)$.

Pozrime sa teraz na očakávanú hodnotu $r$. Platí $P(S[i]=T[j]) = {1 \over \sigma}$, pretože k ľubovoľne zvolenému znaku $S[i]$ existuje práve jeden znak zo $\sigma$, ktorý sa s ním rovná (za predpokladu, že všetky znaky sú v $T$ zastúpené rovnako). Potom $$E(r) = \sum_{\forall i,j} P(S[i]=T[j]) = {nm \over \sigma}$$ V priemernom prípade teda platí odhad časovej zložitosti $O({nm \over \sigma} \log n)$.


