Algorithm Implementation/Strings/Longest common subsequence

public static <E> List<E> LongestCommonSubsequence(E[] s1, E[] s2)
{
        int[][] num = new int[s1.length+1][s2.length+1];  //2D array, initialized to 0
 
        //Actual algorithm
        for (int i = 1; i <= s1.length; i++)
                for (int j = 1; j <= s2.length; j++)
                        if (s1[i-1].equals(s2[j-1]))
                                num[i][j] = 1 + num[i-1][j-1];
                        else
                                num[i][j] = Math.max(num[i-1][j], num[i][j-1]);
 
        System.out.println("length of LCS = " + num[s1.length][s2.length]);
 
        int s1position = s1.length, s2position = s2.length;
        List<E> result = new LinkedList<E>();
 
        while (s1position != 0 && s2position != 0)
        {
                if (s1[s1position - 1].equals(s2[s2position - 1]))
                {
                        result.add(s1[s1position - 1]);
                        s1position--;
                        s2position--;
                }
                else if (num[s1position][s2position - 1] >= num[s1position - 1][s2position])
                {
                        s2position--;
                }
                else
                {
                        s1position--;
                }
        }
        Collections.reverse(result);
        return result;
}

import static java.lang.Math.*;
 
import java.util.ArrayList;
import java.util.List;
/**
 * A class to compute the longest common subsequence in two strings.  
 * Algorithms from Wikipedia:
 * http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
 * 
 * @author jhess
 *
 */
public abstract class LongestCommonSubsequence<VALUE> {
	private int[][] c;
	private ArrayList<DiffEntry<VALUE>> diff;
	private ArrayList<VALUE> backtrack;
 
 
	/**
	 * A constructor for classes inheriting this one, allowing them to 
	 * do some initialization before setting the values of X and Y.  Once 
	 * the initialization is complete, the inheriting class must call
	 * initValues(VALUE[] x, VALUE[] y)
	 */
	protected LongestCommonSubsequence() {
 
	}
 
	protected abstract int lengthOfY() ;
	protected abstract int lengthOfX() ;
	protected abstract VALUE valueOfX(int index) ;
	protected abstract VALUE valueOfY(int index) ;
 
	protected boolean equals(VALUE x1, VALUE y1) {
		return (null == x1 && null == y1) || x1.equals(y1);
	}
 
 
	private boolean isXYEqual(int i, int j) {
		return equals(valueOfXInternal(i),valueOfYInternal(j));
	}
 
	private VALUE valueOfXInternal(int i) {
		return valueOfX(i-1);
	}
 
	private VALUE valueOfYInternal(int j) {
		return valueOfY(j-1);
	}
 
	public void calculateLcs() {
		if(c != null) {
			return;
		}
		c = new int[lengthOfX()+1][];
		for(int i = 0; i < c.length; i++) {
			c[i] = new int[lengthOfY()+1];
		}
 
		for(int i = 1; i < c.length; i++) {
			for(int j = 1; j < c[i].length; j++) {
				if(isXYEqual(i, j)) {
					c[i][j] = c[i-1][j-1] + 1;
				} else {
					c[i][j] = max(c[i][j-1], c[i-1][j]);
				}
			}
		}
	}
 
	public int getLcsLength() {
		calculateLcs();
 
		return c[lengthOfX()][lengthOfY()];
	}
 
	public int getMinEditDistance() {
		calculateLcs();
		return lengthOfX()+lengthOfY()-2*abs(getLcsLength());
	}
 
	public List<VALUE> backtrack() {
		calculateLcs();
		if(this.backtrack == null) {
			this.backtrack = new ArrayList<VALUE>();
			backtrack(lengthOfX(),lengthOfY());
		}
		return this.backtrack;
	}
 
	public void backtrack(int i, int j) {
		calculateLcs();
 
		if (i == 0 || j == 0) {
			return;
		}
		else if (isXYEqual(i, j)) {
			backtrack(i-1,j-1);
			backtrack.add(valueOfXInternal(i));
		} 
		else {
			if(c[i][j-1] > c[i-1][j]) {
				backtrack(i,j-1);
			} else {
				backtrack(i-1,j);
			}
		}
	}
 
	public List<DiffEntry<VALUE>> diff() {
		calculateLcs();
 
		if(this.diff == null) {
			this.diff = new ArrayList<DiffEntry<VALUE>>();
			diff(lengthOfX(),lengthOfY()); 
		}
		return this.diff;
	}
 
	private void diff(int i, int j) {
		calculateLcs();
 
		while(!(i==0 && j==0)) {
			if (i > 0 && j > 0 && isXYEqual(i, j)) {
				this.diff.add(new DiffEntry<VALUE>(DiffType.NONE,
						valueOfXInternal(i)));
				i--;j--;
 
			} else {
				if (j > 0 && (i == 0 || c[i][j - 1] >= c[i - 1][j])) {
					this.diff.add(new DiffEntry<VALUE>(DiffType.ADD,
							valueOfYInternal(j)));
					j--;
 
				} else if (i > 0 && (j == 0 || c[i][j - 1] < c[i - 1][j])) {
 
					this.diff.add(new DiffEntry<VALUE>(DiffType.REMOVE,
							valueOfXInternal(i)));
					i--;
				}
			}
		}
 
		Collections.reverse(this.diff);
	}
 
	@Override
	public String toString() {
		calculateLcs();
 
		StringBuffer buf = new StringBuffer();
		buf.append("  ");
		for(int j = 1; j <= lengthOfY(); j++) {
			buf.append(valueOfYInternal(j));
		}
		buf.append("\n");
		buf.append(" ");
		for(int j = 0; j < c[0].length; j++) {
			buf.append(Integer.toString(c[0][j]));
		}
		buf.append("\n");
		for(int i = 1; i < c.length; i++) {
			buf.append(valueOfXInternal(i));
			for(int j = 0; j < c[i].length; j++) {
				buf.append(Integer.toString(c[i][j]));
			}
			buf.append("\n");
		}
		return buf.toString();
	}
 
	public static enum DiffType {
		ADD("+","add"),REMOVE("-","remove"),NONE(" ","none");
 
		private String val;
		private String name;
 
		DiffType(String val, String name) {
			this.val = val;
			this.name = name;
		}
 
		@Override
		public String toString() {
			return val;
		}
 
		public String getName() {
			return name;
		}
 
		public String getVal() {
			return val;
		}
	}
 
	public static class DiffEntry<VALUE> {
		private DiffType type;
		private VALUE value;
 
		public DiffEntry(DiffType type, VALUE value) {
			super();
			this.type = type;
			this.value = value;
		}
 
		public DiffType getType() {
			return type;
		}
		public void setType(DiffType type) {
			this.type = type;
		}
		public VALUE getValue() {
			return value;
		}
		public void setValue(VALUE value) {
			this.value = value;
		}
 
		@Override
		public String toString() {
			return type.toString()+value.toString();
		}
 
	}
 
 
}

import java.util.List;
 
public class LcsString extends LongestCommonSubsequence<Character> {
	private String x;
	private String y;
 
	public LcsString(String from, String to) {
		this.x = from;
		this.y = to;
	}
 
	protected int lengthOfY() {
		return y.length();
	}
	protected int lengthOfX() {
		return x.length();
	}
	protected Character valueOfX(int index) {
		return x.charAt(index);
	}
	protected Character valueOfY(int index) {
		return y.charAt(index);
	}
 
	public String getHtmlDiff() {
		DiffType type = null;
		List<DiffEntry<Character>> diffs = diff();
		StringBuffer buf = new StringBuffer();
 
		for(DiffEntry<Character> entry : diffs) {
			if(type != entry.getType()) {
				if(type != null) {
					buf.append("</span>");
				}
				buf.append("<span class=\""+entry.getType().getName()+"\">");
				type = entry.getType();
			}
			buf.append(escapeHtml(entry.getValue()));
		}
		buf.append("</span>");
		return buf.toString();
	}
 
	private String escapeHtml(Character ch) {
		switch(ch) {
		case '<' : return "&lt;";
		case '>' : return "&gt;";
		case '"' : return "\&quot;";
		default : return ch.toString();
		}
	}
 
// EXAMPLE.  Here's how you use it.  
	public static void main(String[] args) {
		LcsString seq = new LcsString("<p>the quick brown fox</p>","<p>the <b>Fast</b> brown dog</p>");
		System.out.println("LCS: "+seq.getLcsLength());
		System.out.println("Edit Dist: "+seq.getMinEditDistance());
		System.out.println("Backtrack: "+seq.backtrack());
		System.out.println("HTML Diff: "+seq.getHtmlDiff());
	}
 
}