\begin{slide}{Knuth-Morris-Pratt}

Idee: benutze den minimalen deterministischen Automaten
für $\Sigma^* m \Sigma^*$.

\begin{itemize}
\item nichtdeterministischer Automat mit $|m|+1$ Zuständen
\item Potenzmengenkonstruktion
\item vereinfache die Zustandsbezeichnungen
\item beschreibe Zustandsübergänge durch \emph{failure function}
\item Laufzeit? 
\item Beste/schlechteste Fälle?
\end{itemize}

\end{slide}

\begin{slide}{KMP-Failure-Function}

\begin{eqnarray*}
f &:& \{1\dots|m|\} \to\{0\dots|m|-1\} \\
  & & k\mapsto \max\{i : 0\le i<k \wedge m[1\dots i]=m[k-i+1\dots k] \}
\end{eqnarray*}

Beispiel:
\(
\begin{array}{c|cccccccc}
m & a&a&b&a&b&a&a&b \\ \hline
k & 1&2&3&4&5&6&7&8 \\ \hline
f & 0&1&0&1&0&1&2&3
\end{array}
\)

\bigskip

Rekonstruktion, Beispiel: ($\Sigma=\{a,b\}$)

\[
\begin{array}{c|cccccccccccc}
m &   &   &   &   &   &   & a &   &   &   &   &   \\ \hline
k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline
f &   &   & 1 &   &   &   & 4 &   & 0 & 1 &   & 1       
\end{array}
\]

\end{slide}
