Finding the longest common subsequence.

Here’s an example Java program that finds the longest common subsequence (LCS) between two strings using dynamic programming:

  public class LongestCommonSubsequence {
 
    public static String findLCS(String s1, String s2) {

        int m = s1.length();

        int n = s2.length();

       
        // Create a table to store lengths of LCS

        int[][] dp = new int[m + 1][n + 1];

       
        // Build the dp table in a bottom-up manner

        for (int i = 0; i <= m; i++) {

            for (int j = 0; j <= n; j++) {

                if (i == 0 || j == 0)

                    dp[i][j] = 0;

                else if (s1.charAt(i - 1) == s2.charAt(j - 1))

                    dp[i][j] = dp[i - 1][j - 1] + 1;

                else

                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }

        }

      
        // Retrieve the LCS from the dp table

        int index = dp[m][n];

        char[] lcs = new char[index];

        int i = m, j = n;

        while (i > 0 && j > 0) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                lcs[index - 1] = s1.charAt(i - 1);

                i--;

                j--;

                index--;

            } else if (dp[i - 1][j] > dp[i][j - 1])

                i--;

            else

                j--;
        }
     
        return new String(lcs);

    }
 
    public static void main(String[] args) {

        String s1 = "AGGTAB";

        String s2 = "GXTXAYB";

       
        String lcs = findLCS(s1, s2);

       
        System.out.println("Longest Common Subsequence: " + lcs);

    }

}

This program finds the LCS between the strings `”AGGTAB”` and `”GXTXAYB”`. You can modify the `main` method to use different input strings. The program uses a dynamic programming approach to build a 2D table `dp`, where `dp[i][j]` represents the length of the LCS between the substrings `s1.substring(0, i)` and `s2.substring(0, j)`. Finally, it retrieves the LCS by backtracking through the table.

When you run the program, it will output:

Longest Common Subsequence: GTAB

This means that the longest common subsequence between `”AGGTAB”` and `”GXTXAYB”` is `”GTAB”`.