+\s{Pozorování:}
+Pøedstavme si, ¾e automat u¾ máme hotový a tím, ¾e budeme sledovat jeho chování, chceme zjistit, jak v nìm vedou zpìtné hrany.
+Vezmìme si nìjaký stav $\beta$. To, kam z nìj vede zpìtná hrana zjistíme tak, ¾e spustíme automat na øetìzec $\beta$ bez prvního písmenka a stav, ve kterém se automat zastaví je pøesnì ten, kam má vést i zpìtná hrana z $\beta$. Jinými slovy víme, ¾e $z(\beta) = \alpha (\beta[1:])$.
+Proè takováto vìc funguje? V¹imìme si, ¾e definice $z$ a to, co nám o $\alpha$ øíká invariant je témìø toto¾ná -- $z(\beta)$ je nejdel¹í vlastní suffix $\beta$, který je stavem, $\alpha(\beta)$ je nejdel¹í suffix $\beta$, který je stavem. Jediná odli¹nost je v tom, ¾e definice $z$ narozdíl od definice $\alpha$ zakazuje nevlastní suffixy. Jak nyní vylouèit suffix $\beta$, který by byl roven $\beta$ samotné? Zkrátíme $\beta$ o první znak. Tím pádem v¹echny suffixy $\beta$ bez prvního znaku jsou stejné jako v¹echny vlastní suffixy $\beta$.
+
+K èemu je toto pozorování dobré? Rozmysleme si, ¾e pomocí nìj u¾ doká¾eme zkonstruovat zpìtné hrany. Není to ale trochu divné, kdy¾ pøi simulování automatu na øetìzec bez prvního znaku u¾ zpìtné hrany potøebujeme? Není. Za chvíli zjistíme, ¾e takto mù¾eme zji¹»ovat zpìtné hrany postupnì s tím, ¾e pou¾íváme v¾dy jenom ty, které jsme u¾ sestrojili.
+Takovémuhle pøístupu, kdy pøi konstruování chtìného u¾ pou¾íváme to, co chceme sestrojit, ale pouze ten kousek, který ji¾ máme hotový, se v angliètinì øíká {\I bootstrapping}\foot{Z tohoto slova vzniklo i {\I bootování} poèítaèù, kdy operaèní systém v podstatì zavádí sám seme. Bootstrap znamená èesky ¹truple -- tedy oèko na konci boty, které slou¾í k usnadnìní nazouvání. A jak souvisí ¹truple s algoritmem? To se zase musíme vrátit k pøíbìzích o baronu Prá¹ilovi, mezi nimi¾ je i ten, ve kterém baron Prá¹il vypráví o tom, jak sám sebe vytáhl z ba¾iny za ¹truple. Stejnì tak i my budeme algoritmus konstruovat tím, ¾e se budeme sami vytahovat za ¹truple, tedy bootstrappovat.}.
+V¹imnìme si, ¾e pøi výpoètu se vstupem $\beta$ projde automat jenom prvních $\vert \beta \vert$ stavù. Automat se evidentnì nemù¾e dostat dál, proto¾e na ka¾dý krok dopøedu (doprava) spotøebuje písmenko $\beta$. Tak¾e krokù doprava je maximálnì tolik, kolik je $\vert \beta \vert$. Jinými slovy kdybychom ji¾ mìli zkonstruované zpìtné hrany pro prvních $\vert \beta \vert$ stavù (tedy $0 \dots \vert \beta \vert - 1$), tak pøi tomto výpoètu, kt
+erý potøebujeme na zkonstuovíní zpìtné hrany z $\beta$, je¹tì tuto zpìtnou hranu nemù¾eme potøebovat. Vystaèíme si s tìmi, které ji¾ máme zkonstruované.
+Nabízí se tedy zaèít zpìtnou hranou z prvního znaku (která vede evidentnì do $\varepsilon$), pak postupnì brát dal¹í stavy a pro ka¾dý z nich si spoèítáme kdy spustíme automat na jméno stavu bez prvního znaku a tím získáme dal¹í zpìtnou hranu. Toto funguje, ale je to kvadratické \dots. Máme toti¾ $J$ stavù a pro ka¾dý z nich nám automat bì¾í v èase a¾ lineárním s $J$. Jak z toho ven?
+Z prvního stavu povede zpìtná funkce do $\varepsilon$. Prodl¹í stavy chceme spoèítat zpìtnou funkci. Z druhého stavu $\iota[0:2]$ tedy automat spustíme na $\iota[1:2]$, dále pak na $\iota[1:3]$, $\iota[1:4]$, atd. Ty øetìzce, pro které potøebujeme spo¹tìt automat, abychom dostali zpìtné hrany, jsou tedy ve skuteènosti takové, ¾e ka¾dý dal¹í dostaneme roz¹íøením pøedchozího o jeden znak. To jsou ale pøesnì ty stavy, kterými projde automat pøi spracovávání øetezce $\iota$ od prvního znaku dál. Jedním prùchodem automatu nad jehlou bez prvního písmenka, se tím pádem rovnou dozvíme v¹echny údaje, které potøebujeme.
+Z pøedchozího pozorování plyne, ¾e nikdy nebudeme potøebovat zpìtnou hranu, kterou jsme je¹tì nezkonstruovali a jeliko¾ víme, jedno prohledání trvá lineárnì s délkou toto v èem hledáme, tak toto celé pobì¾í v lineárním èase. Dostaneme tedy následující algoritmus: