Algorithm Implement of Strings -- LCS

/**
 * The Longest common subsequence algorithm
 * created on Aug 2, 2011
 */

package org.mht.strings;

import java.util.ArrayList;
import java.util.Iterator;



public class LCS {

    private int[][] _length;
    private String _x;
    private String _y;
    private ArrayList<Character> _lcs;

    public LCS(String x, String y) {
        _x = x;
        _y = y;
        _length = new int[x.length()+1][y.length()+1];
        }

    public  int LCSLength() {

        for (int i = 0; i <= _x.length(); i++)
            _length[i][0] = 0;
        for (int j = 0; j <= _y.length(); j++)
            _length[0][j] = 0;

        for (int i = 1; i <= _x.length(); i ++) {
            for (int j = 1; j <= _y.length(); j++) {
                if (_x.charAt(i-1) == _y.charAt(j-1))
                    _length[i][j] = _length[i-1][j-1]+1;
                else
                    _length[i][j] = maximum(_length[i][j-1], _length[i-1][j]);
                }
            }
        return _length[_x.length()][_y.length()];
    }

    public static int maximum(int a, int b) {
        return a >= b ? a : b;
    }


    public ArrayList backTrack() {
        LCSLength();
        if(_lcs == null) {
            _lcs = new ArrayList<Character>();
            backTrack(_x.length(), _y.length());
        }

        return _lcs;
    }

    public void backTrack(int i, int j) {
        if ((i == 0) || (j == 0))
            return;
        else if (isEqual(i,j)) {
            backTrack( i-1, j-1);
            _lcs.add(valueOfX(i));
        }
        else {
            if (_length[i-1][j] > _length[i][j-1]) {
                backTrack(i-1,j);
            }
            else
                backTrack(i, j-1);
        }


    }

    public boolean isEqual(int i, int j) {
        return (valueOfX(i).equals(valueOfY(j)));
    }

    public Character valueOfX(int i) {
        return _x.charAt(i-1);
    }

    public Character valueOfY(int j) {
        return _y.charAt(j-1);
    }

    public static void main(String[] args) {
        LCS lcs = new LCS("adfabfdc", "adfadfadabyz");

        ArrayList<Character> result = new ArrayList<Character>();
        result = lcs.backTrack();
        System.out.println("The LCS length is " + lcs.LCSLength());
        System.out.println("The length of result is " + result.size());
        Iterator e = result.iterator();
        System.out.print("The LCS is :");
        while(e.hasNext())
            System.out.print(e.next().toString());

    }

}///:~

/** Algorithm calculating LCS length:
 * function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i-1] = Y[j-1]
                C[i,j] := C[i-1,j-1] + 1
            else:
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

    */

/** Algorithm reading out of an LCS:
 * function backTrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    else if  X[i] = Y[j]
        return backTrack(C, X, Y, i-1, j-1) + X[i]
    else
        if C[i,j-1] > C[i-1,j]
            return backTrack(C, X, Y, i, j-1)
        else
            return backTrack(C, X, Y, i-1, j)

 */

/** Related problems:
 * For two strings X_{1 \dots m} and Y_{1 \dots n}, the length of the shortest common supersequence is related to the length of the LCS by[2]

    \left|SCS(X,Y)\right| = n + m - \left|LCS(X,Y)\right|.

* The edit distance when only insertion and deletion is allowed (no substitution), or when the cost of the substitution is the double of the cost of an insertion or deletion, is:

    d'(X,Y) = n + m - 2 \cdot \left|LCS(X,Y)\right|.
    */