所有最长的公共子序列 [英] All Longest Common Subsequences

问题描述

[注意:我事先搜索过，找不到解决所有子序列LCS问题的建议.]

[NOTE: I searched beforehand and couldn't find advice on solving the LCS problem for all subsequences.]

我在编写最长公共子序列"问题的解决方案时遇到了麻烦，在该问题中，我返回了两个输入字符串的所有最长公共子序列.我查看了维基百科页面，并尝试在其中实施伪代码，但遇到了我的"backtrackAll"方法出现问题.我相信我在下面正确地计算了LCS矩阵，但是我的"backtrackAll"方法返回了一个空集.关于我在做什么的任何提示吗?

I'm having trouble coding up a solution to the "longest common subsequence" problem where I return all the longest common subsequences for two input Strings. I looked at the Wikipedia page and tried to implement the pseudo-code on there, but ran into a problem with my "backtrackAll" method. I believe I'm computing the LCS matrix correctly below, but my "backtrackAll" method returns an empty set. Any tips on what I'm doing wrong?

public static void main (String[] args) {
    String s1 = "AGCAT";
    String s2 = "GAC";
    int[][] matrix = computeMatrix(s1,s2);
    HashSet<String> set = backtrackAll(matrix,s1,s2,s1.length(),s2.length());
    //more stuff would go here...
}

private static int[][] computeMatrix(String s1, String s2) {
    int[][] C = new int[s1.length()+1][s2.length()+1];
    for (int i = 1; i < s1.length()+1; i++) {
        for (int j = 1; j < s2.length()+1; j++) {
            if (s1.charAt(i-1) == s2.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;
}

private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) {
    if (i == 0 || j == 0) {
        return new HashSet<String>();
    } else if (s1.charAt(i-1) == s2.charAt(j-1)) {
        HashSet<String> R = backtrackAll(C,s1,s2,i-1,j-1);
        HashSet<String> new_set = new HashSet<String>();
        for (String Z: R) {
            new_set.add(Z + s1.charAt(i-1));
        }
        return new_set;
    } else {
        HashSet<String> R = new HashSet<String>();
        if (C[i][j-1] >= C[i-1][j]) {
            R = backtrackAll(C, s1, s2, i, j-1);
        } 
        if (C[i-1][j] >= C[i][j-1]) {
            R.addAll(backtrackAll(C,s1,s2,i-1,j));
        }
        return R;
    }
}

推荐答案

我对其进行了一些修改.现在可以使用了.您还应该考虑何时返回null HashSet，在这种情况下，必须添加最后一个匹配的字符.

I modified it a bit. It now works. You should also consider when a null HashSet is returned in whose case the last matched character has to be added.

private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) {
    // System.out.println(i+" " + j);
    if (i == 0 || j == 0) {
        // System.out.println("0t");
        return new HashSet<String>();
    } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
        // System.out.println("2t");
        HashSet<String> R = backtrackAll(C, s1, s2, i - 1, j - 1);
        HashSet<String> new_set = new HashSet<String>();

        for (String Z : R) {
            // System.out.println("1t");
            new_set.add(Z + s1.charAt(i - 1));
        }
        new_set.add("" + s1.charAt(i - 1));
        return new_set;
    } else {
        // System.out.println("3t");
        HashSet<String> R = new HashSet<String>();
        if (C[i][j - 1] >= C[i - 1][j]) {
            R = backtrackAll(C, s1, s2, i, j - 1);
        }
        if (C[i - 1][j] >= C[i][j - 1]) {
            R.addAll(backtrackAll(C, s1, s2, i - 1, j));
        }
        return R;
    }
}

这篇关于所有最长的公共子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！