LCS using DP

	package lcs;
	/**
	* Created by panded4
	*/
	public class LCSTest {
	public static void main(String[] args) {
	LCSTest lcs = new LCSTest();
	String s1 = "DEEP";
	String s2 = "JDEEKPA";
	char[] X = s1.toCharArray();
	char[] Y = s2.toCharArray();
	int m = X.length;
	int n = Y.length;
	lcs.lcs(X, Y, m, n);
	}
	void lcs(char[] X, char[] Y, int m, int n) {
	int L[][] = new int[m + 1][n + 1];
	for (int i = 0; i <= m; i++) {
	for (int j = 0; j <= n; j++) {
	if (i == 0 || j == 0)
	L[i][j] = 0;
	else if (X[i - 1] == Y[j - 1])
	L[i][j] = L[i - 1][j - 1] + 1;
	else
	L[i][j] = max(L[i - 1][j], L[i][j - 1]);
	}
	}
	int index = L[m][n];
	int[] lcs = new int[index + 1];
	int i = m, j = n;
	while (i > 0 && j > 0) {
	if (X[i - 1] == Y[j - 1]) {
	lcs[index - 1] = X[i - 1];
	i--;
	j--;
	index--;
	} else if (L[i - 1][j] > L[i][j - 1])
	i--;
	else
	j--;
	}
	for (int lc : lcs
	) {
	System.out.println((char) lc);
	}
	}
	int max(int a, int b) {
	return (a > b) ? a : b;
	}
	}

view raw LCSTest.java hosted with ❤ by GitHub