\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}
\usepackage {ngerman}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{L\"angste gemeinsame Teilfolge}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

Seien 
$s = s_1 s_2 \dots s_k$ und 
$t = t_1 t_2 \dots t_\ell$
zwei Zeichenketten. 
Wir suchen zun\"achst die L\"ange der
l\"angsten gemeinsamen Teilfolge von
$s$ und $t$.
Sei \texttt{LLGT} ein zweidimensionales
Array vom Typ \texttt{int} mit Dimension
$(k+1) \times (\ell + 1)$.
Wir f\"ullen  \texttt{LLGT} systematisch
gem\"a\ss{} der Rekursion aus der Vorlesung auf.
\begin{verbatim}
// Initialization
for i := 0 to k do
  LLGT[i,0] <- 0 
for j := 0 to l do
  LLGT[0,j] <- 0 
// Implementing the recursion
for i := 1 to k do
  for j := 1 to l do
    if s[i] = t[j] then
      LLGT[i,j] <- 1 + LLGT[i-1, j-1]
    else
      LLGT[i,j] <- max {LLGT[i-1, j], LLGT[i, j-1]}
\end{verbatim}

Das Ergebnis seht in $\texttt{LLGT}[k,\ell]$. Die Laufzeit ist 
$O(k\ell)$. 
Nachdem \texttt{LLGT} berechnet ist, kann man einen
l\"angste gemeinsame Teilfolge finden,
indem man einen Weg durch \texttt{LLGT} rekonstruiert, der zu 
einer optimalen L\"osung f\"uhrt (d.h., wir rekonstruieren 
die Pfeile, die wir in der Vorlesung
in der Tabelle vermerkt hatten). Dies geschieht von hinten.
\begin{verbatim}
  // a stack to store the result
  S <- new Stack
  // start at the end 
  (i,j) <- (k,l)
  while i > 0 and  k > 0 do
    if s[i] = t[j] then
      // if the current symbols are equal, we can include them into the
      // sequence
      (i,j) <- (i-1, j-1)
      S.push(s[i])
    else
      // otherwise we need to determine which of the two choices led to the
      // maximum
      if LLGT[i, j-1] > LLGT[i-1, j] then
        (i, j) <- (i, j-1)
      else
        (i, j) <- (i-1, j)
  // now S contains an optimal subsequence
  while not S.isEmpty() do
    output S.pop()
\end{verbatim}
\end{document}