\h{Slo¾itost}
\itemize\ibull
\:Kroky 2.--5. mají èasovou slo¾itost $\O(\vert \sigma \vert)$, kterou jednodu¹e doká¾eme pomocí potenciálu -- poèet krokù nahoru je men¹í nebo roven poètu krokù dolù. A to je maximálnì $S$.
-\:Kroky 6.--8. mají èasovou slo¾itost $\O(\<poèet výskytù>)$, proto¾e rychleji opravdu nelze v¹echny výskyty vypsat.
+\:Kroky 6.--8. mají èasovou slo¾itost $\O(\<poèet výskytù>)$, proto¾e rychleji doopravdy nelze v¹echny výskyty vypsat.
\endlist
\s{Konstrukce automatu} (Aho, Corasicková)
\:\>\>\>$z(\beta) = \alpha(\beta[1:])$ -- v¹echny zpìtné hrany vedou do vy¹¹ích hladin
\:$z(v) = \<krok>(z(u),c)$
\endlist}
-\figure{Graphic100.eps}{$\<z>(v) = \<krok>(z(u),c)$}{0.7in}
+\figure{Graphic100.eps}{$z(v) = \<krok>(z(u),c)$}{0.7in}
\:$z(r) \leftarrow 0$, do fronty $Q$ pøiøadíme v¹echny syny $r$, pro v¹echny $v$ prvky $Q: z(v) \leftarrow r$.
\:Dokud fronta $Q$ není prázdná:
\::$u\leftarrow$ vybereme z~$Q$.
\:::$R \leftarrow \<krok>(z(u))$ [znak na hranì \<uv>].
\:::$z(v)\leftarrow R$.
-\figure{Graphic101.eps}{}{0.7in}
+\figure{Graphic101.eps}{$z(v) = R$}{0.7in}
\:::Je-li $slovo(R) \not= 0 \Rightarrow \<out>(v) \leftarrow R$, jinak $\<out>(v) \leftarrow \<out>(R)$.
-\figure{Graphic102.eps}{}{0.7in}
+\figure{Graphic102.eps}{Nastavení $\<out>(v)$}{0.7in}
\endalgo
\figure{vyhl_automat_full.eps}{Vyhledávací automat -- kompletní}{1in}
\figure{polynom.eps}{Polynom}{2in}
\ss{Plán:}
-\>Nech» $k=2n-1$, zvolíme $x_0, \ldots, x_k$ libovolná, ale rùzná, a spoèteme $P(x_0), \ldots, P(x_k)$ a $Q(x_0), \ldots, Q(x_k)$.
+
+\>Nech» $k=2^{n-1}$. Zvolíme èísla $x_0, \ldots, x_k$ libovolná, ale rùzná, a spoèteme $P(x_0)$, \dots, $P(x_k)$ a $Q(x_0), \ldots, Q(x_k)$.
Poté $\forall j: y_j=P(x_j)Q(x_j)$
musíme najít polynom $R$ stupnì $\leq k: \forall j: R(x_j)=y_j$.