LCS -- bottom-up (quadratisch) + Übung

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()));
    }
}

Aufgaben:

• vervollständigen Sie die Methode LCS.lcs
• 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: int [][] a wie oben ausrechnen und danach vom Ende zum Anfang durchlaufen (ohne groß zu suchen).

  damit dann die autotool-Aufgaben lösen.