Dynamischer Programmieralgorithmus für die längste gemeinsame Subsequenz in Java

Question

Ich versuche einen dynamischen Programmieralgorithmus für die Längste gemeinsame Subsequenz zu schreiben. Die Rückkehr sollte die Länge dieser Teilsequenz sein. Aber mein Algorithmus gibt immer 0 zurück. Ich konnte den Fehler nicht finden.

public static int LCS(String A, String B, int m, int n) { 
    int table[][] = new int[m + 1][n + 1]; 

    for (int i = 0; i < m; i++) { 
     table[i][0] = 0; 
    } 
    for (int i = 1; i < n; i++) { 
     table[0][n] = 0; 
    } 
    for (int i = 1; i < m; i++) { 
     for (int j = 1; j < n; j++) { 
      if (A.charAt(i) == B.charAt(j)) { 
       table[i][j] = table[i - 1][j - 1] + 1; 
      } else { 
       table[i][j] = max(table[i][j - 1], table[i - 1][j]); 
      } 
     } 
    } 

    return table[m][n]; 
} 

private static int max(int a, int b) { 
    return (a > b) ? a : b; 
} 

public static void main(String args[]) { 
    Scanner in = new Scanner(System.in); 

    System.out.println("Your input words:\n"); 
    String x = in.nextLine(); 
    String y = in.nextLine(); 

    in.close(); 

    int m = x.length(); 
    int n = y.length(); 

    System.out.println("Length of LCS is " + LCS(x, y, m, n)); 
} 

Answer 1

Sieht aus wie Sie this algorithm implementiert, aber haben ein paar Fehler:

• Ihre Schleifen sollten 1..m und 1..ninklusive sein, das heißt, Sie <-<= ändern müssen.

• charAt() ist nullbasiert, Sie benötigen also charAt(i - 1) und charAt(j - 1).

Dies sind keine Fehler, aber:

• Die Schleifen initialisiert auf 0 in Java unnötig sind. table ist durch den Operator new bereits auf alle Nullen initialisiert.

• Keine Notwendigkeit max() zu implementieren, da es bereits als Math.max() implementiert ist.

So, hier ist das Ergebnis, Namen aus dem verlinkten Artikel mit:

public static int LCS(String X, String Y) { 
    final int m = X.length(); 
    final int n = Y.length(); 
    int[][] C = new int[m + 1][n + 1]; 
    for (int i = 1; i <= m; i++) 
     for (int j = 1; j <= n; j++) 
      if (X.charAt(i - 1) == Y.charAt(j - 1)) 
       C[i][j] = C[i - 1][j - 1] + 1; 
      else 
       C[i][j] = Math.max(C[i][j - 1], C[i - 1][j]); 
    return C[m][n]; 
} 

TEST

System.out.println(LCS("This is a test", "Does it work ok?")); 

OUTPUT

5 

Hier sind die passenden Buchstaben der längsten gemeinsamen Teilfolge:

This is a test 
    ↑↑↑ ↑ ↑ 
    ↓↓↓ ↓ ↓ 
Does it work ok? 

Answer 2

Die Bedingungen in den Schlaufen fori < m oder j < n verwenden.

Als Folge i ist nie gleich m und j ist nie gleich n, so wird table[m][n] nie in diesen Schleifen verändern, nicht wahr?

Der zurückgegebene Wert ist der Wert table[m][n], der nie geändert wird: 0.