Longest common subsequence

Longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences

Given two string and find the common sentence in the both

source Code

package com.dsacode.Algorithm.dynamic;
 
import java.util.Arrays;
 
public class LongestCommon {
 
    public static String x = "Hello";
    public static String y = "Helloworld";
 
    public static void main(String [] args) {
        int[][] memo = new int[x.length()+1][y.length()+1];
        for (int i = 0; i < memo.length; i++)
            Arrays.fill(memo[i], -1);
 
        System.out.println("Longest Common String of '"+ x + "' and '"+ y + "' using dynamic programming = "+lcsdyn());
    }
 
    public static int lcsdyn() {
 
        int i,j;
        int lenx = x.length();
        int leny = y.length();
        int[][] table = new int[lenx+1][leny+1];
 
        for (i = 0; i <= lenx; i++)
            table[i][0] = 0;
         
        for (i = 0; i <= leny; i++)
            table[0][i] = 0;
 
        for (i = 1; i <= lenx; i++) {
            for (j = 1; j <= leny; j++) {
                if (x.charAt(i-1) == y.charAt(j-1))
                    table[i][j] = 1+table[i-1][j-1];
                else
                    table[i][j] = Math.max(table[i][j-1], table[i-1][j]);
            }
        }
        return table[lenx][leny];
    }
 
}

Output

Longest Common String of 'Hello' and 'Helloworld' using dynamic programming = 5

Algorithm Explanation

	Pass string arguments to the utility function.
	Take the length of two strings and divide the problems into subproblems.
	Compute the subproblem solution and memorize to improve the time complexity.
	Return solution to the main function and print the solution.

Time Complexity

Reference

1. http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp2.pdf
2. https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
3. https://www.cs.auckland.ac.nz/software/AlgAnim/opt_bin.html