Longest Common Subsequence

Here is an implementation of the Longest Common Subsequence (LCS) problem that was discussed in class.

The Problem
You are given a sequence X = {x1, x2, ..., xm} consisting of m elements and a sequence Y = {y1, y2, ..., yn} consisting of n elements. It is required to find the LCS of X and Y. The elements of the subsequence need not be contiguous.

Here is my solution:



public class LCS {


    int[][] T;
    char[] X;
    char[] Y;


    /**
     * @param args
     */
    public static void main(String[] args) {
        new LCS();
    }


    public LCS() {
        initialize();
        process();
        printLCS(X.length, Y.length);
    }


    /**
     * Does the main processing of the LCS.
     */
    public void process() {
        for (int i = 1; i <= X.length; i++) {
            for (int j = 1; j <= Y.length; j++) {
                if (X[i - 1] == Y[j - 1]) {
                    T[i][j] = 1 + T[i - 1][j - 1];
                } else {
                    T[i][j] = Math.max(T[i][j - 1], T[i - 1][j]);
                }
            }
        }
    }


    /**
     * Sets up two arrays of characters
     */
    public void initialize() {
        X = "ABCBDAB".toCharArray();
        Y = "BDCABA".toCharArray();
        T = new int[X.length + 1][Y.length + 1];
        for (int i = 0; i <= X.length; i++) {
            T[i][0] = 0;
        }
        for (int i = 0; i <= Y.length; i++) {
            T[0][i] = 0;
        }
    }


    public void printResult() {
        for (int i = 0; i <= X.length; i++) {
            for (int j = 0; j <= Y.length; j++) {
                System.out.print(T[i][j]);
            }
            System.out.println();
        }
    }


    public void printLCS(int i, int j) {
        if (i == 0 || j == 0) {
            return;
        } else {
            if (X[i - 1] == Y[j - 1]) {
                printLCS(i - 1, j - 1);
                System.out.print(String.format("%c ", X[i - 1]));
            } else {
                if (T[i - 1][j] > T[i][j - 1]) {
                    printLCS(i - 1, j);
                } else {
                    printLCS(i, j - 1);
                }
            }
        }
    }
}