\begin{slide}{Aufgabenstellung}

  \begin{itemize}
  \item Eingabe:
    \begin{itemize}
    \item ein Wort (Muster) $m$
    \item ein Wort (Ziel) $w$
    \end{itemize}
  \item Ausgabe: die kleinste Zahl $i$,

    für die $m$ ein Präfix von $w_i w_{i+1} \ldots$ ist,

    oder die Feststellung, daß es kein solches $i$ gibt.
  \end{itemize}

 Variante: eine endliche Menge von Mustern $\{m_1,\ldots,m_k\}$

\end{slide}


\begin{slide}{Triviale Lösung}

\begin{verbatim}
outer: 
  for (int i = 0; i < w.length(); i++) {
    for (int j = 0; i < m.length (); j++) {
      if (m[j] != w[i+j]) continue outer;
    }
    return i;
  }
\end{verbatim}
  
  \begin{itemize}
  \item triviale Laufzeit: $O(|w|\cdot|m|)$
  \item läßt sich $O(|w|+|m|)$ erreichen?
  \item \dots unterbieten?
  \end{itemize}




\end{slide}
