最長的公共子序列printdDiff

只是關於最長的Common子序列算法的一個簡短問題。我已經做了，你需要生成序列如下部分：如果我用這個作爲參數最長的公共子序列printdDiff

private static void printDiff(int[][] opt,String x,String y,int i, int j) { 

    if(i>0 &&j>0 && x.charAt(i-1)==y.charAt(j-1)){ 
    printDiff(i-1,j-1); 
    System.out.println(x.charAt(i-1)); 
    } 
    else{ 
     if(j>0&&(i==0||opt[i][j-1]>=opt[i-1][j])){ 
     printDiff(i-1,j-1); 
     System.out.println("-"+y.charAt(j-1)); 
     } 
     else if(i>0&&(j==0|| opt[i][j-1]<=opt[i-1][j])){ 
     printDiff(i-1,j-1); 
     System.out.println(x.charAt(i-1)); 
     } 
    } 

}

然後：

String input1="ABCDE" 
String input2="ACDC" 
int i=input1.length() 
int j=input2.length()

public int[][] lcsLength(char[] input1, char[] input2) { 
    int[][] opt = new int[M][N]; 
    for (int i = 1; i < input1.length; i++) { 
     for (int j = 1; j < input2.length; j++) { 
      if (input1[i] == input2[j]) { 
       opt[i][j] = opt[i - 1][j - 1] + 1; 
      } else { 
       opt[i][j] = Math.max(opt[i][j - 1], opt[i - 1][j]); 
      } 
     } 
    } 
    return opt; 
}

和printDiff功能如下

用lcsLength（）生成opt矩陣之後我希望printdiff woul能給我：

ABCDE- 
A-CD-C

而是我得到：

ABCDE- 
ABCD-C

對我做錯了什麼會幫助我很多

感謝洛朗

來源

2013-02-27 Laurent Morissette

試圖逐步調試算法，通過使用調試器或舊式*打印調試*？ – MrSmith42 2013-02-27 14:15:44

看到我的編輯如下。 – Woot4Moo 2013-02-27 14:18:32

從wiki任何想法：

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j) 
    if i > 0 and j > 0 and X[i] = Y[j] 
     printDiff(C, X, Y, i-1, j-1) 
     print " " + X[i] 
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j]) 
     printDiff(C, X, Y, i, j-1) 
     print "+ " + Y[j] 
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j]) 
     printDiff(C, X, Y, i-1, j) 
     print "- " + X[i] 
    else 
     print ""

此行：

else if(i>0&&(j==0|| opt[i][j-1]<=opt[i-1][j])){

應該是：

else if(i>0&&(j==0|| opt[i][j-1]<opt[i-1][j])){

（改變<=只是<）

來源

2013-02-27 14:15:50 Woot4Moo

不知道，如果它是一個相關的問題，但我覺得你的LCS代碼應該是：

public int[][] lcsLength(char[] input1, char[] input2) { 
    int[][] opt = new int[input1.length+1][input2.length+1]; 
    for (int i = 1; i <= input1.length; i++) { 
     for (int j = 1; j <= input2.length; j++) { 
      if (input1[i-1] == input2[j-1]) { 
       opt[i][j] = opt[i - 1][j - 1] + 1; 
      } else { 
       opt[i][j] = Math.max(opt[i][j - 1], opt[i - 1][j]); 
      } 
     } 
    } 
    return opt; 
}

來源

2013-02-27 14:52:28

最長的公共子序列printdDiff

回答

相關問題