Longest Common Subsequence

LCS.java

public class LongestCommonSubsequence {

	public static int length(String x, String y) {
		int N = x.length();
		int M = y.length();
		int lcs[][] = new int[N + 1][M + 1];
		
		for(int i = 1; i < N + 1; i++) {
			for(int j = 1; j < M + 1; j++) {
				if(x.charAt(i - 1) == y.charAt(j - 1)) {
					lcs[i][j] = lcs[i - 1][j - 1] + 1;
				} else {
					lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
				} 
			}
		}
		return lcs[N][M];
	}
	
	public static void main(String[] args) {
		System.out.println(length("abcs", "abcs"));
		System.out.println(length("abcs", "abs"));
		System.out.println(length("abcs", "as"));
	}
	
}