
\begin{slide}{LCS -- eingeschr�nkt linear}

Suche nach einer LCS $=$ Suchen eines kurzen Pfades
von \verb|(0,0)| nach \verb|(xs.length-1, ys.length-1)|.

einzelne Kanten verlaufen (siehe Quelltext)
\begin{itemize}
\item nach rechts: $(i-1,j) \to (i,j)$
 \quad
 Buchstabe aus \verb|xs|
\item nach unten: $(i,j-1) \to (i,j)$
  \quad
 Buchstabe aus \verb|ys|
\item nach rechts unten (diagonal):  $(i-1,j-1) \to (i,j)$

  gemeinsamer Buchstabe
\end{itemize}
Optimierungen:
\begin{itemize}
\item
  Suche nur in der N�he der Diagonalen
\item
  Beginne Suche von beiden Endpunkten
\end{itemize}

\end{slide}
