
\begin{slide}{LCS --- bottom-up (quadratisch) $+$ Übung}
\begin{small}
\begin{verbatim}
class LCS {

    // bestimmt größte Länge einer gemeinsamen Teilfolge
    static int lcs (char [] xs, char [] ys) {
        int a[][] = new int [xs.length][ys.length];
        for (int i=0; i<xs.length; i++) {
            for (int j=0; j<ys.length; j++) {
                // Ziel:
                // a[i][j] enthält größte Länge einer gemeinsamen Teilfolge
                // von xs[0 .. i] und ys[0 ..j]
            }
        }
        return get (a, xs.length-1, ys.length-1);
    }

    // liefert Wert aus Array oder 0, falls Indizes zu klein sind
    static int get (int [][] a, int i, int j) {
        if ((i < 0) || (j <0)) {
            return 0;
        } else {
            return a[i][j];
        }
    }

    public static void main(String[] args) {
        String xs = "ABCABBA";
        String ys = "CBABAC";
        System.out.println (lcs (xs.toCharArray(), ys.toCharArray()));
    }
}
\end{verbatim}
\end{small}
Aufgaben:
\begin{itemize}
\item
  vervollständigen Sie die Methode \verb|LCS.lcs|
\item
  bauen Sie eine Möglichkeit ein, nicht nur die Länge einer längsten
  gemeinsamen Teilfolge zu bestimmen, sondern auch eine solche Folge selbst auszugeben.

  Hinweis: \verb|int [][] a| wie oben ausrechnen und \emph{danach}
  vom Ende zum Anfang durchlaufen (ohne groß zu suchen).

  damit dann die autotool-Aufgaben lösen.
\end{itemize}
\end{slide}

