\section{Využitie najnižšieho spoločného predka na vyhľadávanie v texte}

Na minulej prednáške sme ukázali, že hodnoty $LCA(u,v)$ vieme počítať v~konštantnom čase s predspracovaním $\mathcal{O}(n)$. V sufixových stromoch, kde máme listy pre sufixy $S[i..n]$ a $S[j..n]$, je hodnotou $LCA(i,j)$ vrchol pre najdlhší spoločný prefix $S[i..n]$ a $S[j..n]$.

\subsection{Hľadanie palindrómov}

Lca sa dá využiť aj pri hľadaní palindrómov. Palindróm je reťazec, ktorý sa odpredu číta rovnako ako odzadu, teda $S = S^R$. 
Maximálny palindróm v $S$ je podslovo $S[i..j]$, ktoré je palindróm a $S[i-1] \neq S[j+1]$, teda sa nedá rozšíriť.

Všetky maximálne palindrómy pre nejaký sufixový strom vieme nájsť v čase $O(n)$. Vytvoríme zovšeobecnený sufixový strom, kam vložíme $S$ aj $S_R$.
Budeme testovať všetky možné stredy palindrómu. Zvlášť budeme robiť palindrómy párnej a nepárnej dĺžky. \\
\indent Nech má palindróm nepárnu dĺžku, teda $2j+1$. 
Nech je stred na pozícii $i$. Potom musí platiť: S[i+1 ... i+j] = $S^R$[n-i+2 ... n - i + j + 1]. Chceme nájsť najdlhší spoločný prefix
S[i+1 ... n] a $S^R$[n - i + 2 ... n]. Stačí zavolať $lca(S_{i+1}, S^R_{n-i+2})$. Index $j$ je dĺžka reťazca zodpovedajúceho vrcholu $v$.
Podobne budeme postupovať aj pre párne dĺžky palindrómu.

\subsection{Hľadanie približných výskytov $P$ v $T$ v Hammingovej vzdialenosti}

Ďalej môžeme lca využiť aj v súvislosti s Hammingovou vzdialenosťou.
Hammingova vzdialenosť $d_H(S_1,S_2)$ medzi reťazcami $S_1$ a $S_2$ rovnakej dĺžky je počet pozícií, takých že platí $S_1[i] \neq S_2[i]$.\\
\indent Ukážeme ako pre dané $T$ a $P$ nájsť všetky $i$, pre ktoré platí $d_H(T[i .. i + m - 1], P) \le k$, t.j. namiesto presných výskytov $P$ v $T$ hľadáme približné výskyty. 

\paragraph{Prístup 1} 
Zostrojíme sufixový strom pre $P$ a $T$ a potom pre každú pozíciu v texte zisťujeme, či sa tam dá nájsť približný výskyt. 
\begin{verbatim}
for(i = 1; i <= n - m + 1; i ++){
   j = 1;
   err = 0;
   while(j <= m){
      q = dĺžka max. spoločného prefixu T[i + j - 1 .. n] a P[j .. m] 
      // nájdeme pomocou lca
      // P[j .. j + q - 1] = T[i + j - 1 .. i + j + q - 2]
      if (j + q  <= m){
         err ++;
         if (err > k){
            break;
         }
      }
      j = j + q + 1   //presunieme sa za chybu
   }
   if (err <= k){
     print i;
   }
}
\end{verbatim}
Pretože chýb bude nanajvýš $k$, celková zložitosť tohto algoritmu bude $O(nk)$.


\paragraph{Prístup 2} Tento prístup nemá nič spoločné s LCA. Hodí sa, keď máme veľa vzoriek nad malou abecedou.  Zostavíme si sufixový strom len pre $T$. Potom budeme skúmať všetky reťazce $P'$ také, že $d_H(P,P') \le k$. Budeme zisťovať, či $P'$ je podslovo $T$ (sledujeme cestu v strome). Prvý krok beží v čase $\mathcal{O}(n)$, posledný v čase $\mathcal{O}(m)$ pre každé $P'$. Počet rôznych $P'$ vyrátame nasledovne: máme najviac $i\le k$ chýb, musíme uvažovať $i$ pozícií chýb a na každej nový znak, čo je  
$$
\sum_{i=0}^k \binom{m}{i} (\sigma -1)^i,
$$
čo je najviac $\mathcal{O}((m\sigma)^k)$. Takže celková zložitosť je $O(n+m^{k+1}\sigma^k)$. To je výhodné, ak máme veľa vzoriek a malú abecedu. Využíva sa to napríklad aj v bioinformatike, keď hľadáme (napr. v DNA) kúsok, na ktorý sa napr. viaže molekula rozpoznávajúca určitý motív (vzorku), v ktorej sa môže vyskytovať chyba, tj. nechceme presný výskyt. Napríklad pre ľudský genóm môžeme mať $n$ napr. rádovo $10^9$, veľkosť abecedy je 4 a môžeme uvažovať veľa vzoriek, napr. dĺžky cca $m=10$ s $k=2$ chybami.

\subsection{Najdlhší podreťazec viacerých reťazcov}
Ďalšiou aplikáciou $LCA$ je zovšeobecnený sufixový strom pre $z$ reťazcov $\{S_1,\dots,S_z\}$. Úlohou je vyrátať hodnotu $C(v)$ -- počet rôznych reťazcov $S_i$ s listom v podstrome s~koreňom $v$. Ak by sme túto hodnotu vedeli zrátať, vedeli by sme sa pýtať, aké je najdlhšie podslovo, ktoré sa vyskytuje v každom reťazci. (Pozrieme všetky vrcholy a~hľadáme najhlbší taký, ktorý má ešte hodnotu $z$.) Môžeme sa tiež pýtať, aké je najdlhšie podslovo, ktoré sa vyskytuje v aspoň $k$ reťazcoch.

\begin{figure}[h]
  \centerline{\includegraphics{figures/l11-c_strom.1}}
  \caption{Príklad stromu s hodnotami $C(v)$.}
\end{figure}


\paragraph{Jednoduchý algoritmus.} Ukážeme si najprv jednoduchší spôsob -- v každom vrchole si budeme pamätať zoznam $S_i$, potom hodnota $C(v)$ je dĺžka tohto zoznamu. Začneme od listov, ktorým priradíme im prislúchajúci reťazec. Problém je v tom, že časová zložitosť je $\mathcal{O}(nz)$, lebo otcovi rátame zoznam ako zjednotenie zoznamov jeho synov. Preto pre veľké $z$ je tento algoritmus neefektívny.

\paragraph{Rýchlejší algoritmus} Zostrojíme algoritmus s časovou zložitosťou $\mathcal{O}(n)$ pomocou funkcie $LCA$. Algoritmus najprv prejde strom do hĺbky a urobí zoznam listov v poradí, ako sa cez nich prechádzalo. (t.j. graficky zľava doprava) Rozhádžeme si tento zoznam na $z$ zoznamov $L_1,\dots, L_z $, pričom $L_i$ obsahuje sufixy pre reťazec $S_i$. 

Potom prejdeme cez každý zo zoznamov $L_i$ a~spočítame $LCA$ pre každé dva prvky, ktoré idú za sebou v tomto zozname. Tieto zoznamy majú dokopy dĺžku $n$, $LCA$ vieme rátať v konštatnom čase, takže zatiaľ je celý algoritmus lineárny. Navyše si pre každý vrchol počítame, koľkokrát bol ten vrchol $LCA$. (V premennej $h(v)$.) Nech $s(v)$ je súčet hodnôt $h(v)$ v podstrome s koreňom $v$. Spočítame ich zdola hore v lineárnom čase, lebo $$ s(v) = \sum_{w \in \mathrm{child}(v)} s(w) + h(v).$$ 

Spočítame taktiež v premennej $l(v)$ počet listov v podstrome s koreňom $v$, čo môžeme tiež rátať zdola hore ako súčet pre všetky deti, pričom listy majú hodnotu 1. Potom tvrdíme, že $C(v) = l(v) - s(v)$ a výsledok dostaneme v $\mathcal{O}(n)$. Prečo je hodnota $C(v)$ takáto? 

\begin{figure}[h]
  \centerline{\includegraphics{figures/l11-podstrom.1}}
  \caption{Podstrom s koreňom $v$ a listy, pre ktoré bude výsledok $LCA$ v tomto podstrome.}\label{fig:3}
\end{figure}


Uvažujme vrchol $v$ a reťazec $S_i$. Nech sa $S_i$ v podstrome z koreňom $v$ vyskytuje $k$-krát. (Nech $k$ listov patrí k $S_i$.) Potom ak $k>0$, tak chceme tento reťazec započítať jeden krát. V $l(v)$ je zarátaný $k$-krát a v $s(v)$ je zarátaný $k-1$ krát. (Keď sa pozrieme na tie listy, tvoria nejaký interval -- sú pokope ako na obrázku \ref{fig:3} a pre každé dva vedľa seba zavoláme $LCA$. Hodnota $s(v)$ udáva počet, koľko krát výsledok $LCA$ ``spadol'' do tohto podstromu, a to je pre každú dvojicu, ktorá je vo vnútri, tj $k-1$ dvojíc.) Preto je rozdiel $l(v)-s(v)$ rovný $1$. Ak $k=0$, tak aj $l(v) = 0 $, aj $s(v) = 0$. (Každá dvojica je mimo podstromu, preto aj ich predok musí byť tiež mimo podstromu.) 

\subsection{TODO: Vypisovanie dokumentov}

Preložiť, spísať (S. Muthukrishnan,  Efficient algorithms for document retrieval problems. SODA 2002: 657-666 )

We have array $A$ precomputed for RMQ.\\
For given $i$, $j$, $x$ find all indices $k\in \{i,\dots,j\}$ 
s.t. $A[k]\le x$.

\begin{lstlisting}
void small(i,j,x) {
  if(j>i) return;
  k = rmq(i,j);
  if(a[k]<=x) { 
    print k;
    small(i,k-1);
    small(k+1,j);
  }
}
\end{lstlisting}
cas vypoctu: O(p), kde p je pocet vypisanych indexov (kazdemu najdenemu k zapocitaj dve dcerske rekurzivne volania - celkovy pocet volani je najviac 2p+1) 

Preprocess texts $\{S_1,\dots,S_z\}$\\
Query: which documents contain pattern $P$?\\
We can do $O(m+k)$ where $k=$number of occurrences of $P$\\
Want $O(m+p)$ where $p=$number of documents containing $P$

Array of leaves $L$ in DFS order\\
For leaf $L[i]$ let $A[i]$ be the index of previous leaf from the same $S_j$

Occurrences of $P$: subtree of corresponding to interval $[i,j]$ in $L$\\
Find all $k\in [i,\dots,j]$ that have $A[k]<i$

Running time? Preprocessing?




