\begin{slide}{LCS}

Idee: die beiden Aufgaben sind äquivalent:
\begin{itemize}
\item
  kürzeste Edit-Sequenz finden 
\item
  längste gemeinsame Teilfolge 
  (longest common subsequence) finden
\end{itemize}

Beispiel:
\newcommand{\bx}[1]{\fbox{\ensuremath{#1}}}
$y = AB\bx{C}\bx{AB}B\bx{A}, 
z = \bx{C}B\bx{AB}\bx{A}C$

für $x = CABA$ gilt $x \le y$ und $x \le z$, 

wobei die Relation $\le$ auf $\Sigma^*$ so definiert ist:

$u \le v$, falls man $v$ aus $u$ 
durch \emph{Löschen} einiger Buchstaben erhält 
(jedoch \emph{ohne} die Reihenfolge der übrigen Buchstaben zu ändern)

vgl. mit Ausgabe von \verb|diff|

\end{slide}




