Consider the Longest Common Subsequence (LCS) problem. You are given two strings A and B and you are to return the longest common subsequence in A and B. A subsequence of a string is defined to be the initial string with 0 or more characters removed. For example if A=”MOHAMED”, B=”AHMED”, the length of the LCS of A and B is 4 ( “HMED” or “AMED” …

LCS.java

public class LCS {

    public static void main(String[] args) {
        String mohamed = "MOHAMED";
        String ahmed = "AHMED";
        int dpMatrix[][] = new int[mohamed.length() + 1][ahmed.length() + 1];
        for (int i = 0; i <= mohamed.length(); i++)
            for (int j = 0; j <= ahmed.length(); j++)
                if (i == 0 || j == 0)
                    dpMatrix[i][j] = 0;
                else if (mohamed.charAt(i - 1) == ahmed.charAt(j - 1))
                    dpMatrix[i][j] = dpMatrix[i - 1][j - 1] + 1;
                else
                    dpMatrix[i][j] = Math.max(dpMatrix[i - 1][j], dpMatrix[i][j - 1]);
        System.out.print(" ");
        for (int i = 0; i < ahmed.length(); i++)
            System.out.print(" " + ahmed.charAt(i));
        
        for (int i = 1; i <= mohamed.length(); i++)
            for (int j = 1; j <= ahmed.length(); j++)
                System.out.print(((j == 1) ? "\n" + mohamed.charAt(i - 1) + " " : " ") + dpMatrix[i][j]);

        System.out.println("\nresult: " + dpMatrix[mohamed.length()][ahmed.length()]);

    }

}

|SampleOutput

  A H M E D
M 0 0 1 1 1
O 0 0 1 1 1
H 0 1 1 1 1
A 1 1 1 1 1
M 1 1 2 2 2
E 1 1 2 3 3
D 1 1 2 3 4
result: 4