Breaking
Dynamic programming

# 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;

for (i = 0; i <= leny; i++)
table[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
```