Longest common subsequence difference

Question

I have a program that I am writing in Java and have to do 2 things, find the longest common sub-sequence and align the common characters. The LCS works just fine but the align part just loops away or do nothing.

I try to do this algorithm which I found on Wikipedia

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 ""

Here is the code I wrote (I removed the LCS part)

static char[] input1 = "ABCDE".toCharArray();
static char[] input2 = "ACDC".toCharArray();
static int M = input1.length;
static int N = input2.length;
static int[][] opt = new int[M + 1][N + 1];

public static void printDiff(int opt[][], char input1[], char input2[]) {
    int i = 0, j = 0;
    while (i < input1.length && j < input2.length) {
    if (i > 0 && j > 0 && input1[i] == input2[j]) {
        System.out.print("  " + input1[i]);
        i++;
        j++;
    } else if (j > 0 && (i == 0 || opt[i][j - 1] >= opt[i - 1][j])) {
        System.out.print("+ " + input2[j]);
        j++;
    } else if (i > 0 && (j == 0 || opt[i][j - 1] < opt[i - 1][j])) {
        System.out.print("- " + input1[i]);
        i++;
    } else {
        System.out.print("");

    }
    }
}

Gilbert Le Blanc · Accepted Answer

I rewrote your code to use the Wikipedia algorithm. In other words, I used recursion rather than a where clause. I had to change one of the if conditions because Java is zero index based and the Wikipedia algorithm is one index based.

I had to add the LCS function back in so that I could calculate the int[][]opt.

I added parenthesis to the if statements to make sure that the operations were done in the order I wanted them done.

I also fixed the output. The Wikipedia algorithm had "+ " and "- " as output. That appears to be a typo. The output should be " +" and " -", respectively.

Here's my version of the code.

public class PrintDiff {

    char[]  input1  = "ABCDE".toCharArray();
    char[]  input2  = "ACDC".toCharArray();
    int     M       = input1.length;
    int     N       = input2.length;

    public void run() {
        int[][] opt = lcsLength(input1, input2);
        printDiff(opt, input1, input2, M - 1, N - 1);
    }

    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;
    }

    public void printDiff(int opt[][], char input1[], char input2[], int i,
            int j) {
        if ((i >= 0) && (j >= 0) && (input1[i] == input2[j])) {
            printDiff(opt, input1, input2, i - 1, j - 1);
            System.out.print("  " + input1[i]);
        } else if ((j > 0) && ((i == 0) || (opt[i][j - 1] >= opt[i - 1][j]))) {
            printDiff(opt, input1, input2, i, j - 1);
            System.out.print(" +" + input2[j]);
        } else if ((i > 0) && ((j == 0) || (opt[i][j - 1] < opt[i - 1][j]))) {
            printDiff(opt, input1, input2, i - 1, j);
            System.out.print(" -" + input1[i]);
        } else {
            System.out.print("");
        }
    }

    public static void main(String[] args) {
        new PrintDiff().run();
    }

}

And here's my output.

  A -B  C  D -E +C

Longest common subsequence difference

Answers (2)

Related Questions