/* Dynamic Programming implementation of LCS problem */ #include    using namespace std; // Maximum string length #define N 100 int L[N][N]; /* Returns set containing all LCS for X[0..m-1] Y[0..n-1] */ set<string> findLCS(string X string Y int m int n) {  // construct a set to store possible LCS  set<string> s;  // If we reaches end of either string return  // a empty set  if (m == 0 || n == 0)  {  s.insert('');  return s;  }  // If the last characters of X and Y are same  if (X[m - 1] == Y[n - 1])  {  // recurse for X[0..m-2] and Y[0..n-2] in  // the matrix  set<string> tmp = findLCS(X Y m - 1 n - 1);  // append current character to all possible LCS  // of substring X[0..m-2] and Y[0..n-2].  for (string str : tmp)  s.insert(str + X[m - 1]);  }  // If the last characters of X and Y are not same  else  {  // If LCS can be constructed from top side of  // the matrix recurse for X[0..m-2] and Y[0..n-1]  if (L[m - 1][n] >= L[m][n - 1])  s = findLCS(X Y m - 1 n);  // If LCS can be constructed from left side of  // the matrix recurse for X[0..m-1] and Y[0..n-2]  if (L[m][n - 1] >= L[m - 1][n])  {  set<string> tmp = findLCS(X Y m n - 1);  // merge two sets if L[m-1][n] == L[m][n-1]  // Note s will be empty if L[m-1][n] != L[m][n-1]  s.insert(tmp.begin() tmp.end());  }  }  return s; } /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ int LCS(string X string Y int m int n) {  // Build L[m+1][n+1] in bottom up fashion  for (int i = 0; i <= m; i++)  {  for (int j = 0; j <= n; j++)  {  if (i == 0 || j == 0)  L[i][j] = 0;  else if (X[i - 1] == Y[j - 1])  L[i][j] = L[i - 1][j - 1] + 1;  else  L[i][j] = max(L[i - 1][j] L[i][j - 1]);  }  }  return L[m][n]; } /* Driver program to test above function */ int main() {  string X = 'AGTGATG';  string Y = 'GTTAG';  int m = X.length();  int n = Y.length();  cout << 'LCS length is ' << LCS(X Y m n) << endl;  set<string> s = findLCS(X Y m n);  for (string str : s)  cout << str << endl;  return 0; } 

/* Dynamic Programming implementation of LCS problem */ import java.util.*; class GFG { // Maximum String length static int N = 100; static int [][]L = new int[N][N]; /* Returns set containing all LCS for   X[0..m-1] Y[0..n-1] */ static Set<String> findLCS(String X   String Y int m int n) {  // construct a set to store possible LCS  Set<String> s = new HashSet<>();  // If we reaches end of either String   // return a empty set  if (m == 0 || n == 0)  {  s.add('');  return s;  }  // If the last characters of X and Y are same  if (X.charAt(m - 1) == Y.charAt(n - 1))  {  // recurse for X[0..m-2] and Y[0..n-2]   // in the matrix  Set<String> tmp = findLCS(X Y m - 1 n - 1);  // append current character to all possible LCS  // of subString X[0..m-2] and Y[0..n-2].  for (String str : tmp)  s.add(str + X.charAt(m - 1));  }  // If the last characters of X and Y are not same  else  {  // If LCS can be constructed from top side of  // the matrix recurse for X[0..m-2] and Y[0..n-1]  if (L[m - 1][n] >= L[m][n - 1])  s = findLCS(X Y m - 1 n);  // If LCS can be constructed from left side of  // the matrix recurse for X[0..m-1] and Y[0..n-2]  if (L[m][n - 1] >= L[m - 1][n])  {  Set<String> tmp = findLCS(X Y m n - 1);  // merge two sets if L[m-1][n] == L[m][n-1]  // Note s will be empty if L[m-1][n] != L[m][n-1]  s.addAll(tmp);  }  }  return s; } /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ static int LCS(String X String Y int m int n) {  // Build L[m+1][n+1] in bottom up fashion  for (int i = 0; i <= m; i++)  {  for (int j = 0; j <= n; j++)  {  if (i == 0 || j == 0)  L[i][j] = 0;  else if (X.charAt(i - 1) == Y.charAt(j - 1))  L[i][j] = L[i - 1][j - 1] + 1;  else  L[i][j] = Math.max(L[i - 1][j]  L[i][j - 1]);  }  }  return L[m][n]; } // Driver Code public static void main(String[] args) {  String X = 'AGTGATG';  String Y = 'GTTAG';  int m = X.length();  int n = Y.length();  System.out.println('LCS length is ' +  LCS(X Y m n));  Set<String> s = findLCS(X Y m n);  for (String str : s)  System.out.println(str); } } // This code is contributed by 29AjayKumar 

# Dynamic Programming implementation of LCS problem # Maximum string length N = 100 L = [[0 for i in range(N)] for j in range(N)] # Returns set containing all LCS  # for X[0..m-1] Y[0..n-1] def findLCS(x y m n): # construct a set to store possible LCS s = set() # If we reaches end of either string return # a empty set if m == 0 or n == 0: s.add('') return s # If the last characters of X and Y are same if x[m - 1] == y[n - 1]: # recurse for X[0..m-2] and Y[0..n-2] in # the matrix tmp = findLCS(x y m - 1 n - 1) # append current character to all possible LCS # of substring X[0..m-2] and Y[0..n-2]. for string in tmp: s.add(string + x[m - 1]) # If the last characters of X and Y are not same else: # If LCS can be constructed from top side of # the matrix recurse for X[0..m-2] and Y[0..n-1] if L[m - 1][n] >= L[m][n - 1]: s = findLCS(x y m - 1 n) # If LCS can be constructed from left side of # the matrix recurse for X[0..m-1] and Y[0..n-2] if L[m][n - 1] >= L[m - 1][n]: tmp = findLCS(x y m n - 1) # merge two sets if L[m-1][n] == L[m][n-1] # Note s will be empty if L[m-1][n] != L[m][n-1] for i in tmp: s.add(i) return s # Returns length of LCS for X[0..m-1] Y[0..n-1] def LCS(x y m n): # Build L[m+1][n+1] in bottom up fashion for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: L[i][j] = 0 else if x[i - 1] == y[j - 1]: L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j] L[i][j - 1]) return L[m][n] # Driver Code if __name__ == '__main__': x = 'AGTGATG' y = 'GTTAG' m = len(x) n = len(y) print('LCS length is' LCS(x y m n)) s = findLCS(x y m n) for i in s: print(i) # This code is contributed by # sanjeev2552 

// Dynamic Programming implementation  // of LCS problem  using System; using System.Collections.Generic;    class GFG { // Maximum String length static int N = 100; static int []L = new int[N N]; /* Returns set containing all LCS for  X[0..m-1] Y[0..n-1] */ static HashSet<String> findLCS(String X   String Y  int m int n) {  // construct a set to store possible LCS  HashSet<String> s = new HashSet<String>();  // If we reaches end of either String   // return a empty set  if (m == 0 || n == 0)  {  s.Add('');  return s;  }  // If the last characters of X and Y are same  if (X[m - 1] == Y[n - 1])  {  // recurse for X[0..m-2] and Y[0..n-2]   // in the matrix  HashSet<String> tmp = findLCS(X Y m - 1 n - 1);  // append current character to all possible LCS  // of subString X[0..m-2] and Y[0..n-2].  foreach (String str in tmp)  s.Add(str + X[m - 1]);  }  // If the last characters of X and Y are not same  else  {  // If LCS can be constructed from top side of  // the matrix recurse for X[0..m-2] and Y[0..n-1]  if (L[m - 1 n] >= L[m n - 1])  s = findLCS(X Y m - 1 n);  // If LCS can be constructed from left side of  // the matrix recurse for X[0..m-1] and Y[0..n-2]  if (L[m n - 1] >= L[m - 1 n])  {  HashSet<String> tmp = findLCS(X Y m n - 1);  // merge two sets if L[m-1n] == L[mn-1]  // Note s will be empty if L[m-1n] != L[mn-1]  foreach (String str in tmp)  s.Add(str);  }  }  return s; } /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ static int LCS(String X String Y int m int n) {  // Build L[m+1n+1] in bottom up fashion  for (int i = 0; i <= m; i++)  {  for (int j = 0; j <= n; j++)  {  if (i == 0 || j == 0)  L[i j] = 0;  else if (X[i - 1] == Y[j - 1])  L[i j] = L[i - 1 j - 1] + 1;  else  L[i j] = Math.Max(L[i - 1 j]  L[i j - 1]);  }  }  return L[m n]; } // Driver Code public static void Main(String[] args) {  String X = 'AGTGATG';  String Y = 'GTTAG';  int m = X.Length;  int n = Y.Length;  Console.WriteLine('LCS length is ' +  LCS(X Y m n));  HashSet<String> s = findLCS(X Y m n);  foreach (String str in s)  Console.WriteLine(str); } }   // This code is contributed by Rajput-Ji 

<script> /* Dynamic Programming implementation of LCS problem */ // Maximum String length let N = 100; let L = new Array(N); for(let i=0;i<N;i++) {  L[i]=new Array(N);   } /* Returns set containing all LCS for   X[0..m-1] Y[0..n-1] */ function findLCS(XYmn) {  // construct a set to store possible LCS  let s = new Set();    // If we reaches end of either String   // return a empty set  if (m == 0 || n == 0)  {  s.add('');  return s;  }    // If the last characters of X and Y are same  if (X[m-1] == Y[n-1])  {  // recurse for X[0..m-2] and Y[0..n-2]   // in the matrix  let tmp = findLCS(X Y m - 1 n - 1);    // append current character to all possible LCS  // of subString X[0..m-2] and Y[0..n-2].  for (let str of tmp.values())  s.add(str + X[m-1]);  }    // If the last characters of X and Y are not same  else  {  // If LCS can be constructed from top side of  // the matrix recurse for X[0..m-2] and Y[0..n-1]  if (L[m - 1][n] >= L[m][n - 1])  s = findLCS(X Y m - 1 n);    // If LCS can be constructed from left side of  // the matrix recurse for X[0..m-1] and Y[0..n-2]  if (L[m][n - 1] >= L[m - 1][n])  {  let tmp = findLCS(X Y m n - 1);    // merge two sets if L[m-1][n] == L[m][n-1]  // Note s will be empty if L[m-1][n] != L[m][n-1]    for (let item of tmp.values())  s.add(item)  }  }  return s; } /* Returns length of LCS for X[0..m-1] Y[0..n-1] */ function LCS(XYmn) {  // Build L[m+1][n+1] in bottom up fashion  for (let i = 0; i <= m; i++)  {  for (let j = 0; j <= n; j++)  {  if (i == 0 || j == 0)  L[i][j] = 0;  else if (X[i-1] == Y[j-1])  L[i][j] = L[i - 1][j - 1] + 1;  else  L[i][j] = Math.max(L[i - 1][j]  L[i][j - 1]);  }  }  return L[m][n]; } // Driver Code let X = 'AGTGATG'; let Y = 'GTTAG'; let m = X.length; let n = Y.length; document.write('LCS length is ' +  LCS(X Y m n)+'  
'); let s = findLCS(X Y m n); for (let str of s.values())  document.write(str+'  
'); // This code is contributed by rag2127 </script>