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

class LCS {
  // größte Länge einer gemeinsamen Teilfolge
  static int lcs (String xs, String ys) {
    int a[][] = 
        new int [ ... ] [ ... ]
    for (int i = ... ; ... ; ... ) {
      for (int j = ... ; ... ; ... ) {
        // Spezifikation:
        // a[i][j] enthält größte Länge 
        // einer gemeinsamen Teilfolge
        // von xs.substring(i) 
        // und ys.substring(j) 
      }
    }
    return ...
  }
  @Test
  public void test1 () {
      assertEquals (4, lcs ("ABCABBA","CBABAC"));
  }
}

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.