LCS.java

public class LCS {
    public static void main(String[] args) {
        String s1 = args[0];
        String s2 = args[1];
        System.out.println(Sequence(s1, s2));
    }

    public static int Length(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        int[][] LCS_len = new int[l1 + 1][l2 + 1];
        for (int i = l1 - 1; i >= 0; i--) {
            for (int j = l2 - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j))
                    LCS_len[i][j] = LCS_len[i + 1][j + 1] + 1;
                else
                    LCS_len[i][j] = Math.max(LCS_len[i + 1][j], LCS_len[i][j + 1]);
            }
        }
        return LCS_len[0][0];
    }

    public static String Sequence(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        int[][] LCS_len = new int[l1 + 1][l2 + 1];
        String sequence = "";
        for (int i = l1 - 1; i >= 0; i--) {
            for (int j = l2 - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    LCS_len[i][j] = LCS_len[i + 1][j + 1] + 1;
                }
                else {
                    LCS_len[i][j] = Math.max(LCS_len[i + 1][j], LCS_len[i][j + 1]);
                }
            }
        }
        int i = 0, j = 0;
        while (i < l1 && j < l2) {
            if (s1.charAt(i) == s2.charAt(j)) {
                sequence += s1.charAt(i);
                i++;
                j++;
            }
            else if (LCS_len[i][j + 1] >= LCS_len[i + 1][j]) j++;
            else i++;
        }
        return sequence;
    }
}