2

最長共通サブシーケンス アルゴリズムについての簡単な質問です。次のように、サブシーケンスを生成する必要がある部分を実行しました。

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 関数は次のようになります。

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

lcsLength() で opt マトリックスを生成した後、printdiff が私に与えてくれることを望みます:

ABCDE-
A-CD-C

しかし、代わりに私は得る:

ABCDE-
ABCD-C

私が何を間違えたのかについてのアイデアは、私を大いに助けてくれるでしょう

ありがとうローラン

4

2 に答える 2

0

ウィキから：

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-27T14:15:50.283 に答える
0

関連する問題かどうかはわかりませんが、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-27T14:52:28.637 に答える