\input ../sgr.tex

\prednaska{10}{Suffixové stromy}{}

V~této kapitole popí¹eme jednu pozoruhodnou datovou strukturu, pomocí ní¾ doká¾eme problémy týkající
se øetìzcù pøevádìt na grafové problémy a øe¹it je tak v~lineárním èase.

\h{Øetìzce, trie a suffixové stromy}

\ss{Definice:}

\nointerlineskip
\halign{\qquad#\dotfill&~#\hfil\cr
\hbox to 0.35\hsize{}\cr
$\Sigma$					& koneèná abeceda -- mno¾ina znakù \cr
\omit						& (znaky budeme znaèit latinskými písmeny)\cr
$\Sigma^*$					& mno¾ina v¹ech slov nad $\Sigma$ \cr
\omit						& (slova budeme znaèit øeckými písmeny)\cr
$\varepsilon$					& prázdné slovo\cr
$\vert\alpha\vert$				& délka slova $\alpha$\cr
$\alpha\beta$					& zøetìzení slov $\alpha$ a $\beta$ ($\alpha\varepsilon=\varepsilon\alpha=\alpha$)\cr
$\alpha^R$					& slovo $\alpha$ napsané pozpátku\cr
$\alpha$ je {\I prefixem} $\beta$		& $\exists\gamma: \beta=\alpha\gamma$ ($\beta$ zaèíná na~$\alpha$)\cr
$\alpha$ je {\I suffixem} $\beta$		& $\exists\gamma: \beta=\gamma\alpha$ ($\beta$ konèí na~$\alpha$)\cr
$\alpha$ je {\I podslovem} $\beta$		& $\exists\gamma,\delta: \beta=\gamma\alpha\delta$ (znaèíme $\alpha \subset \beta$)\cr
$\alpha$ je {\I vlastním prefixem} $\beta$	& je prefixem a $\alpha\ne\beta$ \cr
\omit						& (analogicky vlastní suffix a podslovo)\cr
}

\s{Pozorování:} Prázdné slovo je prefixem, suffixem i podslovem ka¾dého slova vèetnì sebe sama.
Podslova jsou právì prefixy suffixù a také suffixy prefixù.

\s{Definice:} {\I Trie ($\Sigma$-strom)} pro koneènou mno¾inu slov $X\subset\Sigma^*$ je orientovaný graf $G=(V,E)$, kde:
\itemize\relax
\:$V = \{\alpha: \alpha\hbox{ je prefixem nìjakého $\beta\in X$} \},$
\:$(\alpha,\beta)\in E \equiv \exists x\in\Sigma: \beta=\alpha x$.
\endlist

\s{Pozorování:} Trie je strom s koøenem $\varepsilon$. Jeho listy jsou slova z $X$, která nejsou vlastními prefixy jiných slov z~$X$.
Hrany si mù¾eme pøedstavit popsané písmeny, o~nì¾ prefix roz¹iøují, popisky hran na~cestì z~koøene do~vrcholu~$\alpha$ dávají právì slovo~$\alpha$.

\s{Definice:} {\I Komprimovaná trie ($\Sigma^+$-strom)} vznikne z trie nahrazením maximálních nevìtvících se cest hranami. Hrany
jsou tentokrát popsané øetìzci místo jednotlivými písmeny, pøièem¾ popisky v¹ech hran vycházejících z~jednoho vrcholu se li¹í v~prvním
znaku. Vrcholùm \uv{uvnitø hran} (které padly za obì» kompresi) budeme øíkat {\I skryté vrcholy.}

\s{Definice:} {\I Suffixový strom (ST)} pro slovo $\sigma\in\Sigma^*$ je komprimovaná trie pro $X=\{\alpha: \hbox{$\alpha$ je suffixem $\sigma$}\}$.

\s{Pozorování:} Vrcholy suffixového stromu (vèetnì skrytých) odpovídají prefixùm suffixù slova~$\sigma$,
tedy v¹em jeho podslovùm. Listy stromu jsou suffixy, které se v~$\sigma$ ji¾ nikde jinde nevyskytují
(takovým suffixùm budeme øíkat {\I nevnoøené}). Vnitøní vrcholy odpovídají {\I vìtvícím podslovùm,}
tedy podslovùm $\alpha\subset\sigma$ takovým, ¾e $\alpha a\subset\sigma$ i $\alpha b\subset\sigma$
pro nìjaké dva rùzné znaky~$a$,~$b$.

Nìkdy mù¾e být nepraktické, ¾e nìkteré suffixy neodpovídají listùm (proto¾e jsou vnoøené), ale
s~tím se mù¾eme snadno vypoøádat: pøidáme na~konec slova~$\sigma$ nìjaký znak~$\$$, který se nikde
jinde nevyskytuje. Neprázdné suffixy slova $\sigma\$$ odpovídají suffixùm slova~$\sigma$
a ¾ádný z~nich nemù¾e být vnoøený. Takový suffixový strom budeme znaèit ST\$.

\s{Pøíklad:}

\figure{baraba.eps}{Suffixy slova \uv{baraba}: trie, suffixový strom, ST s~dolarem}{\epsfxsize}

\>Nyní jak je to s~konstrukcí suffixových stromù:

\s{Lemma:} Suffixový strom pro slovo $\sigma$ délky $n$ je reprezentovatelný v~prostoru $\O(n)$.

\proof Strom má $\O(n)$ listù a ka¾dý vnitøní vrchol má alespoò $2$ syny, tak¾e vnitøních
vrcholù je také $\O(n)$. Hran je rovnì¾ lineárnì. Nálepky na~hranách staèí popsat
poèáteèní a koncovou pozicí v~$\sigma$.
\qed

\s{Vìta:} Suffixový strom pro slovo $\sigma$ délky $n$ lze sestrojit v~èase $\O(n)$.

\proof Ve~zbytku této kapitoly pøedvedeme dvì rùzné konstrukce v~lineárním èase.
\qed

\s{Aplikace} -- co v¹e doká¾eme v~lineárním èase, kdy¾ umíme lineárnì konstruovat ST:

\nobreak

\numlist\ndotted
\:{\I Inverzní vyhledávání} (tj. pøedzpracujeme si v~lineárním èase text a pak umíme pro libovolné
slovo~$\alpha$ v~èase $\O(\vert\alpha\vert)$ rozhodnout, zda se v~textu vyskytuje)\foot{Èili pøesný
opak toho, co~umí vyhledávací automat -- ten si pøedzpracovává dotaz.} -- staèí sestrojit~ST
a pak jej procházet od~koøene. Také umíme najít v¹echny výskyty (odpovídají suffixùm, které mají
jako prefix hledané slovo, tak¾e staèí vytvoøit ST\$ a vypsat v¹echny listy pod
nalezeným vrcholem) nebo pøímo vrátit jejich poèet (pøedpoèítáme si pomocí DFS pro ka¾dý vrchol,
kolik pod ním le¾í listù).

\:{\I Nejdel¹í opakující se podslovo} -- takové podslovo je v~ST\$ nutnì vìtvící, tak¾e staèí
najít vnitøní vrchol s~nejvìt¹í {\I písmenkovou hloubkou} (tj. hloubkou mìøenou ve~znacích
místo ve~hranách).

\:{\I Histogram èetností podslov délky~$k$} -- rozøízneme ST\$ v~písmenkové hloubce~$k$ a spoèítáme,
kolik pùvodních listù je pod ka¾dým novým.

\:{\I Nejdel¹í spoleèné podslovo} slov~$\alpha$ a $\beta$ -- postavíme ST pro slovo $\alpha\$_1\beta\$_2$,
jeho listy odpovídají suffixùm slov $\alpha$ a $\beta$. Tak¾e staèí pomocí DFS najít nejhlub¹í vnitøní
vrchol, pod kterým se vyskytují listy pro~$\alpha$ i $\beta$. Podobnì mù¾eme sestrojit ST\$ pro libovolnou
mno¾inu slov.\foot{Jen si musíme dát pozor, abychom si moc nezvìt¹ili abecedu; jak moc si ji
mù¾eme dovolit zvìt¹it, vyplyne z~konkrétních konstrukcí.}

\:{\I Nejdel¹í palindromické podslovo} (tj. takové $\beta\subset\alpha$, pro nì¾ je $\beta^R=\beta$)
-- postavíme spoleèný ST\$ pro slova $\alpha$ a $\alpha^R$. Postupnì procházíme pøes v¹echny mo¾né støedy
palindromického podslova a v¹imneme si, ¾e takové slovo je pro ka¾dý støed nejdel¹ím spoleèným
prefixem podslova od~tohoto bodu do~konce a podslova od~tohoto bodu pozpátku k~zaèátku,
èili nìjakého suffixu $\alpha$ a nìjakého suffixu $\alpha^R$. Tyto suffixy ov¹em odpovídají
listùm sestrojeného ST a jejich nejdel¹í spoleèný prefix je nejbli¾¹ím spoleèným pøedchùdcem
ve~stromu, tak¾e staèí pro strom vybudovat datovou strukturu pro spoleèné pøedchùdce
a s~její pomocí doká¾eme jeden støed prozkoumat v~konstantním èase.

\:{\I Burrows-Wheelerova Transformace} \cite{burrows:bwt} -- jejím základem je lexikografické setøídìní v¹ech
rotací slova~$\sigma$, co¾ zvládneme sestrojením ST pro slovo~$\sigma\sigma$, jeho
uøíznutím v~písmenkové hloubce~$\vert\sigma\vert$ a vypsáním novì vzniklých listù v~poøadí
\uv{zleva doprava}.
\endlist

\s{Cvièení:} Zkuste vymyslet co nejlep¹í algoritmy pro tyto problémy bez pou¾ití~ST.

\h{Suffixová pole}

\>V~nìkterých pøípadech se hodí místo suffixového stromu pou¾ívat kompaktnìj¹í datové struktury.

\s{Notace:} Pro slovo $\sigma$ bude $\sigma[i]$ znaèit jeho $i$-tý znak (èíslujeme od~nuly),
$\sigma[i:j]$ pak podslovo $\sigma[i]\sigma[i+1]\ldots\sigma[j-1]$. Libovolnou z~mezí mù¾eme vynechat, proto
$\sigma[i:{}]$ bude suffix od~$i$ do~konce a $\sigma[{}:j]$ prefix od~zaèátku do~$j-1$.
Pokud $j\le i$, definujeme $\sigma[i:j]$ jako prázdné slovo, tak¾e prázdný suffix mù¾eme
napøíklad zapsat jako $\sigma[\vert\sigma\vert:{}].$

${\rm LCP}(\alpha,\beta)$ bude znaèit délku nejdel¹ího spoleèného prefixu slov $\alpha$ a $\beta$,
èili nejvìt¹í $i\le \vert\alpha\vert,\vert\beta\vert$ takové, ¾e $\alpha[{}:i]=\beta[{}:i]$.

\s{Definice:} {\I Suffixové pole (Suffix Array)} $A_\sigma$ pro slovo $\sigma$ délky~$n$ je posloupnost v¹ech suffixù
slova~$\sigma$ v~lexikografickém poøadí. Mù¾eme ho reprezentovat napøíklad jako permutaci $A$ èísel
$0,\ldots,n$, pro ní¾ $\sigma[A[0]:{}] < \sigma[A[1]:{}] < \ldots < \sigma[A[n]:{}]$.

\s{Definice:} {\I Pole nejdel¹ích spoleèných prefixù (Longest Common Prefix Array)} $L_\sigma$ pro slovo $\sigma$ je posloupnost,
v~ní¾ $L_\sigma[i]:={\rm LCP}(A_\sigma[i],A_\sigma[i+1])$.

\s{Vìta:} Suffixový strom pro slovo $\sigma\$$ a dvojici $(A_\sigma,L_\sigma)$ na sebe lze
v~lineárním èase pøevádìt.

\proof Kdy¾ projdeme ST($\sigma\$$) do hloubky, poøadí listù odpovídá posloupnosti $A_\sigma$ a písmenkové hloubky vnitøních
vrcholù v~inorderu odpovídají $L_\sigma$. Naopak ST($\sigma\$$) získáme tak, ¾e sestrojíme kartézský strom
pro~$L_\sigma$ (získáme vnitøní vrcholy ST), doplníme do~nìj listy, pøiøadíme jim suffixy podle~$A_\sigma$
a nakonec podle listù rekonstruujeme nálepky hran.
\qed

\h{Rekurzivní konstrukce}

\>Uká¾eme algoritmus, který pro slovo $\sigma\in\Sigma^*$ délky~$n$ sestrojí jeho suffixové pole
a LCP pole v~èase $\O(n+{\rm Sort}(n,\Sigma))$, kde ${\rm Sort}(\ldots)$ je èas potøebný pro setøídìní
$n$~symbolù z~abecedy~$\Sigma$. V~kombinaci s~pøedchozími výsledky tedy dostaneme lineární konstrukci
ST($\sigma$) pro libovolnou fixní abecedu.

\s{Algoritmus:} (Konstrukce $A$ a $L$ podle Kärkkäinena a Sanderse \cite{karkkainen03simple})

\algo
\:Redukujeme abecedu na~$1\ldots n$: ve~vstupním slovu je nejvý¹e $n$ rùzných znakù,
tak¾e je staèí setøídit a pøeèíslovat.

\:Definujeme slova $\sigma_0$, $\sigma_1$, $\sigma_2$ následovnì:
$$\eqalign{
\sigma_0[i] &:= \left<\sigma[3i],\sigma[3i+1],\sigma[3i+2]\right>\cr
\sigma_1[i] &:= \left<\sigma[3i+1],\sigma[3i+2],\sigma[3i+3]\right>\cr
\sigma_2[i] &:= \left<\sigma[3i+2],\sigma[3i+3],\sigma[3i+4]\right>\cr
}$$
V¹echna $\sigma_k$ jsou slova délky $\approx n/3$ nad~abecedou velikosti $n^3$. Dovolíme
si mírnì zneu¾ívat notaci a pou¾ívat symbol $\sigma_k$ i jejich pøepis do~abecedy pùvodní.

\:Zavoláme algoritmus rekurzivnì na slovo $\sigma_0\sigma_1$, èím¾ získáme $A_{01}$ a $L_{01}$.
(Suffixy slova $\sigma_0\sigma_1$ odpovídají suffixùm slov $\sigma_0$ a~$\sigma_1$.)

\:Spoèítáme pole $P_0$ a $P_1$, která nám budou øíkat, kde se v~$A_{01}$ vyskytuje
který suffix slov $\sigma_0$ a~$\sigma_1$. Tedy $A_{01}[P_0[i]]=i$, $A_{01}[P_1[i]] = i+\vert\sigma_0\vert$.
Jinými slovy, $P_0$ a~$P_1$ budou èásti inverzní permutace k~$A_{01}$. V¹imnìte si,
¾e platí $P_i[x] < P_j[y]$ právì tehdy, kdy¾ $\sigma_i[x:{}] < \sigma_j[y:{}]$, tak¾e
suffixy slov $\sigma_0$ a~$\sigma_1$ od této chvíle umíme porovnávat v~èase~$\O(1)$.

\:Vytvoøíme~$A_2$ (suffixové pole pro~$\sigma_2$): Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:\nobreak{}\nobreak] = \sigma[3i+2]\sigma_0[i+1:{}]$,
odpovídá lexikografické poøadí suffixù $\sigma_2[i:{}]$ poøadí dvojic $(\sigma[3i+2],P_0[i+1])$.
Tyto dvojice ov¹em mù¾eme setøídit dvìma prùchody pøihrádkového tøídìní.

\:Slijeme $A_{01}$ a~$A_2$ do~$A$: sléváme dvì setøídìné posloupnosti,
tak¾e staèí umìt jejich prvky v~konstantním èase porovnat:
$$\eqalign{
\sigma_0[i:{}] < \sigma_2[j:{}] \Leftrightarrow{} &\sigma[3i:{}] < \sigma[3j+2:{}] \cr
                                \Leftrightarrow{} &\sigma[3i]\,\sigma_1[i:{}] < \sigma[3j+2]\,\sigma_0[j+1:{}],\cr
\sigma_1[i:{}] < \sigma_2[j:{}] \Leftrightarrow{} &\sigma[3i+1:{}] < \sigma[3j+2:{}] \cr
                                \Leftrightarrow{} &\sigma[3i+1]\,\sigma[3i+2]\,\sigma_0[i+1:{}] < \cr
                                                  &\sigma[3j+2]\,\sigma[3j+3]\,\sigma_1[j+1:{}].\cr
}$$
Poka¾dé tedy porovnáme nejvý¹e dvì dvojice znakù a pak dvojici suffixù slov $\sigma_0$ a $\sigma_1$,
k~èemu¾ nám pomohou pole $P_0$ a~$P_1$.

\:Dopoèítáme $L$:
   \::Pokud v~$A$ sousedí suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_{0,1}$,
      sousedí tyto dva suffixy i v~$A_{01}$, tak¾e jejich LCP najdeme pøímo v~$L$.
   \::Setkají-li se dva suffixy slova~$\sigma_2$, v¹imneme si, ¾e
      $\sigma_2[i:{}] = \sigma[3i+2:\nobreak{}] = \sigma[3i+2]\,\sigma_0[i+1:{}]$.
      ${\rm LCP}(\sigma_2[i:{}],\sigma_2[j:{}])$ je tedy buïto~0 (pokud $\sigma[3i+2]\ne\sigma[3j+2]$),
      nebo $1+3\cdot{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}])$, pøípadnì toté¾ zvý¹ené
      o~1 nebo~2, pokud se trojznaky v~$\sigma_0$ následující po LCP zèásti shodují.
      Pøitom ${\rm LCP}(\sigma_0[p:{}],\sigma_0[q:{}])$ spoèítáme pomocí~$L$.
      Je to toti¾ minimum intervalu v~$L$ mezi indexy $P_0[p]$ a~$P_0[q]$. To zjistíme
      v~konstantním èase pomocí struktury pro intervalová minima.
   \::Pokud se setká suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_2$, staèí
      tyto suffixy pøepsat podobnì jako v~6.~kroku a problém tím opìt pøevést
      na výpoèet LCP dvou suffixù slov~$\sigma_{0,1}$.

\endalgo

\s{Analýza èasové slo¾itosti:} Tøídìní napoprvé trvá ${\rm Sort}(n,\Sigma)$, ve~v¹ech
rekurzivních voláních u¾ je lineární (trojice èísel velikosti $\O(n)$ mù¾eme tøídit tøíprùchodovým
pøihrádkovým tøídìním s~$\O(n)$ pøihrádkami). Z~toho dostáváme:
$$T(n) = T(2/3\cdot n) + \O(n),~\hbox{a tedy}~T(n)=\O(n).$$
\qed

\h{Ukkonenova inkrementální konstrukce}

\>Ukkonen popsal algoritmus \cite{ukkonen95line} pro konstrukci suffixového stromu bez dolarù,
pracující inkrementálnì: Zaène se stromem pro prázdné slovo a postupnì na konec slova pøidává
dal¹í znaky a pøepoèítává strom. Ka¾dý znak pøitom pøidá v~amortizovanì konstantním èase.
Pro slovo~$\sigma$ tedy doká¾e sestrojit ST v~èase $\O(\vert\sigma\vert)$.

Budeme pøedpokládat, ¾e hrany vedoucí z~jednoho vrcholu je mo¾né indexovat jejich
prvními písmeny -- to bezpeènì platí, pokud je abeceda pevná; není-li, mù¾eme
si pomoci he¹ováním.

\s{Pozorování:} Kdy¾ slovo~$\sigma$ roz¹íøíme na~$\sigma a$, ST se zmìní následovnì:

\numlist\ndotted
\:V¹echny stávající vrcholy stromu (vèetnì skrytých) odpovídají podslovùm slova~$\sigma$.
  Ta jsou i podslovy $\sigma a$, tak¾e se budou nacházet i v~novém stromu.
\:Pokud $\beta$ bylo vìtvící slovo, zùstane nadále vìtvící -- tedy vnitøní vrcholy ve~stromu zùstanou.
\:Ka¾dý nový suffix~$\beta a$ vznikne prodlou¾ením nìjakého pùvodního suffixu~$\beta$. Pøitom:
  \itemize\ibull
  \:Pokud byl~$\beta$ nevnoøený suffix (èili byl reprezentovaný listem), ani $\beta a$
    nebude vnoøený. Z~toho víme, ¾e listy zùstanou listy, pouze jim potøebujeme prodlou¾it
    nálepky. Aby to netrvalo pøíli¹ dlouho, zavedeme {\I otevøené hrany,} jejich¾ nálepka
    øíká \uv{od~pozice~$i$ do konce}. Listy se tak o~sebe postarají samy.
  \:Pokud $\beta$ byl vnoøený suffix (tj. vnitøní èi skrytý vrchol):
    \itemize\ibull
      \:Buï se $\beta a$ vyskytuje v~$\sigma$, a tím pádem je to vnoøený suffix nového slova
        a strom není nutné upravovat;
      \:nebo se $\beta a$ v~$\sigma$ nevyskytuje -- tehdy pro nìj musíme zalo¾it nový list
        s~otevøenou hranou a pøípadnì i nový vnitøní vrchol, pod ním¾ bude tento list pøipojen.
    \endlist
  \endlist
\endlist

Víme tedy, co v¹echno je pøi roz¹íøení slova potøeba ve~stromu upravit.
Zbývá vyøe¹it, jak to udìlat efektivnì.

\s{Vnoøené suffixy:}
Pøedev¹ím potøebujeme umìt rozpoznat, které suffixy jsou vnoøené a které nikoliv.
K~tomu se hodí v¹imnout si, ¾e vnoøené suffixy tvoøí souvislý úsek:

{\narrower
\s{Lemma:} Je-li $\alpha$ vnoøený suffix slova~$\sigma$ a $\beta$ je suffix slova~$\alpha$,
pak $\beta$ je v~$\sigma$ také vìtvící.

\proof
Ve~slovì sigma se vyskytuje $\alpha x$ a $\alpha y$ pro nìjaké dva rùzné znaky $x$ a~$y$.
Ka¾dý z~tìchto výskytù pøitom konèí výskytem slova~$\beta$, jednou následovaným~$x$,
podruhé~$y$.
\qed

}

\>Staèí si tedy zapamatovat nejdel¹í vnoøený suffix slova~$\sigma$. Tomu budeme øíkat
{\I aktivní suffix} a budeme ho znaèit $\alpha(\sigma)$. Libovolný suffix~$\beta\subseteq\sigma$
pak bude vnoøený právì tehdy, kdy¾ $\vert\beta\vert \le \vert\alpha(\sigma)\vert$.

Aktivní suffix tedy tvoøí hranici mezi nevnoøenými a vnoøenými suffixy. Jak se tato
hranice posune, kdy¾ slovo~$\sigma$ roz¹íøíme? Na to je odpovìï snadná:

{\narrower
\s{Lemma:} Pro ka¾dé $\sigma$, $a$ platí: $\alpha(\sigma a)$ je suffixem $\alpha(\sigma)a.$

\proof
$\alpha(\sigma a)$ i $\alpha(\sigma)a$ jsou suffixy slova $\sigma a$, a~proto staèí porovnat jejich délky.
Slovo $\beta := \hbox{\uv{$\alpha(\sigma a)$ bez koncového~$a$}}$ je vnoøeným suffixem v~$\sigma$, tak¾e
$\vert\beta\vert \le \vert\alpha(\sigma)\vert$, a~tedy také $\vert\alpha(\sigma a)\vert = \vert\beta a\vert \le \vert\alpha(\sigma)a\vert$.
\qed

}

\>Hranice se tedy mù¾e posouvat pouze doprava, pøípadnì zùstat na místì.
Toho lze snadno vyu¾ít.

\s{Idea algoritmu:} Udr¾ujeme si $\alpha=\alpha(\sigma)$ a pøi pøidání znaku $a$ zkontrolujeme,
zda $\alpha a$ je stále vnoøený suffix. Pokud ano, nic se nemìní, pokud ne, pøidáme nový list
a pøípadnì také vnitøní vrchol, $\alpha$ zkrátíme zleva o~znak a testujeme dál.

\s{Analýza:} Po~pøidání jednoho znaku na konec slova~$\sigma$ provedeme amortizovanì
konstantní poèet úprav stromu (ka¾dá úprava slovo $\alpha$ zkrátí, po v¹ech úpravách
pøidáme k~$\alpha$ jediný znak). Tudí¾ staèí ukázat, jak provést ka¾dou úpravu
v~(amortizovanì) konstantním èase. K~tomu potøebujeme ¹ikovnou reprezentaci slova~$\alpha$,
která bude umìt efektivnì prodlu¾ovat zprava, zkracovat zleva a testovat existenci
vrcholu ve~stromu.

\s{Definice:} {\I Referenèní pár} pro slovo $\alpha\subseteq\sigma$ je dvojice
$(\pi,\tau)$, v~ní¾ $\pi$ je vrchol stromu, $\tau$ libovolné slovo a $\pi\tau=\alpha$.
Navíc víme, ¾e $\tau\subseteq\sigma$, tak¾e si~$\tau$ staèí pamatovat jako dvojici
indexù ve~slovì~$\sigma$.

Referenèní pár je {\I kanonický,} pokud neexistuje hrana vedoucí z~vrcholu~$\pi$ s~nálepkou,
která by byla prefixem slova~$\tau$. (V¹imnìte si, ¾e taková hrana se pozná podle toho,
¾e první znak nálepky se shoduje s~prvním znakem slova~$\tau$ a nálepka není del¹í ne¾
slovo~$\tau$. Shodu ostatních znakù není nutné kontrolovat.)

\s{Pozorování:} Ke~ka¾dému slovu $\alpha\subseteq\sigma$ existuje právì jeden kanonický
referenèní pár, který ho popisuje. To je ze~v¹ech referenèních párù pro toto slovo
ten s~nejdel¹ím~$\pi$ (nejhlub¹ím vrcholem).

\s{Definice:} Zpìtná hrana $\<back>(\pi)$ vede z~vrcholu $\pi$ do~vrcholu,
který je zkrácením slova~$\pi$ o~jeden znak zleva. (Nahlédneme, ¾e takový
vrchol musí existovat: pokud je $\pi$ vnitøní vrchol, pak je slovo~$\pi$
vìtvící, tak¾e ka¾dý jeho suffix musí také být vìtvící, a~tím pádem také
odpovídat nìjakého vrcholu.)

\s{Operace s~referenèními páry:}
S~referenèním párem $(\pi,\tau)$ popisujícím slovo~$\alpha$ potøebujeme provádìt
následujicí operace:

\itemize\ibull
\:{\I Pøidání znaku~$a$ na konec:} Pøipí¹eme~$a$ na konec slova~$\tau$.
  To je jistì referenèní pár pro $\alpha a$, ale nemusí být kanonický.
  Pøitom mù¾eme snadno ovìøit, zda se $\alpha a$ ve~stromu nachází,
  a pøípadnì operaci odmítnout.
\:{\I Odebrání znaku ze~zaèátku:} Pokud $\pi$ není koøen stromu, polo¾íme
  $\pi\leftarrow\<back>(\pi)$ a zachováme~$\tau$. Pokud naopak je~$\pi$
  prázdný øetìzec, odebereme z~$\tau$ jeho první znak (to lze udìlat
  v~konstantním èase, proto¾e~$\tau$ je reprezentované dvojicí indexù do~$\sigma$).
\:{\I Pøevedení na kanonický tvar:} Obì pøedchozí operace mohou vytvoøit referenèní
  pár, který není kanonický. Poka¾dé proto kanonicitu zkontrolujeme a pøípadnì
  pár upravíme. Ovìøíme, zda hrana z~$\pi$ indexovaná písmenem~$a$ není
  dost krátká na to, aby byla prefixem slova~$\tau$. Pokud je, tak se
  po~této hranì pøesuneme dolù, èím¾~$\pi$ prodlou¾íme a~$\tau$ zkrátíme,
  a proces opakujeme. Jeliko¾ tím poka¾dé $\tau$~zkrátíme a kdykoliv jindy
  se $\tau$ prodlou¾í nejvý¹e o~1, mají v¹echny pøevody na kanonický tvar
  amortizovanì konstantní slo¾itost.
\endlist

\>Nyní ji¾ mù¾eme doplnit detaily, získat celý algoritmus a nahlédnout,
¾e pracuje v~amortizovanì konstantním èase.

\s{Algoritmus podrobnìji:}

\algo
\:{\I Vstup:} $\alpha=\alpha(\sigma)$ reprezentovaný jako kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma$ spolu s~hranami \<back>, nový znak~$a$.
\:Zjistíme, jestli $\alpha a$ je pøítomen ve~stromu, a pøípadnì ho zalo¾íme:
\::Pokud $\tau=\varepsilon$: ($\alpha=\pi$ je vnitøní vrchol)
\:::Vede-li z~vrcholu $\pi$ hrana s~nálepkou zaèínající znakem $a$, pak je pøítomen.
\:::Nevede-li, není pøítomen, a~tak pøidáme novou otevøenou hranu vedoucí z~$\pi$ do~nového listu.
\::Pokud $\tau\ne\varepsilon$: ($\alpha$ je skrytý vrchol)
\:::Najdeme hranu, po~ní¾ z~$\pi$ pokraèuje slovo $\tau$ (která to je, poznáme podle prvního znaku slova~$\tau$).
\:::Pokud v~popisce této hrany po~$\tau$ následuje znak~$a$, pak je $\alpha a$ pøítomen.
\:::Pokud nenásleduje, tak nebyl pøítomen, èili tuto hranu rozdìlíme: pøidáme na~ni nový vnitøní vrchol,
    do~nìj¾ povede hrana s~popiskou~$\tau$ a z~nìj zbytek pùvodní hrany a otevøená hrana do~nového listu.
\:Pokud $\alpha a$ nebyl pøítomen, tak $\alpha$ zkrátíme a vrátíme se na~krok~2.
\:Nyní víme, ¾e $\alpha a$ ji¾ byl pøítomen, tak¾e upravíme referenèní pár, aby popisoval $\alpha a$.
\:Dopoèítáme zpìtné hrany (viz ní¾e).
\:{\I Výstup:} $\alpha=\alpha(\sigma a)$ jako kanonický referenèní pár $(\pi,\tau)$, $T$ suffixový strom pro~$\sigma a$
  a jeho zpìtné hrany \<back>.
\endalgo

\s{Zpìtné hrany:}
Zbývá dodat, jak nastavovat novým vrcholùm jejich zpìtné hrany. To potøebujeme
jen pro vnitøní vrcholy (na~zpìtné hrany z~listù se algoritmus nikdy neodkazuje).
V¹imneme si, ¾e pokud jsme zalo¾ili vrchol, odpovídá tento vrchol v¾dy souèasnému~$\alpha$
a zpìtná hrana z~nìj povede do~zkrácení slova~$\alpha$ o~znak zleva, co¾ je
pøesnì vrchol, který zalo¾íme (nebo zjistíme, ¾e u¾ existuje) v~pøí¹tí iteraci
hlavního cyklu. V~dal¹í iteraci je¹tì urèitì nebudeme tuto hranu potøebovat,
proto¾e $\pi$ v¾dy jen zkracujeme, a~tak mù¾eme vznik zpìtné hrany o~iteraci
zpozdit. Výroba zpìtné hrany tedy bude také trvat jen konstantnì dlouho.

\references
\bye
