Java : align characters

[Metraon]

Hello

I have made a chunk of java code based on this algorithm I read 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 ""

The goal is to align chars DNA style, with a simple algorithm.

    public static 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(input1[i]);

        }
        
    }

For example, it should do this :

Input (2 char arrays)
ABCDE
ACDC

Expected output
ABCDE-
A-CD-C

Actual output
A-C-D-C

The problem seems that the loop detect the difference but it doesnt add +1 in my matrix when there is a mismatch. So it keeps seeing mismatch for the rest of my characters, or something like that...

I want to use this algorithm because the program will be translated to assembly language, so no complex libraries, no objects etc etc etc

Thanks !

 

[aL Mac]

Is Opt a similarity matrix and where are you generating that?

 

[Metraon]

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

}

Here is my class. I want to align the characters like DNA sequence alignement. The problem is the algorythm is quite dumb. It seems to see all the differences and not align them.