// C++ program to find all LCS of two strings in // sorted order. #include   #define MAX 100 using namespace std; // length of lcs int lcslen = 0; // dp matrix to store result of sub calls for lcs int dp[MAX][MAX]; // A memoization based function that returns LCS of // str1[i..len1-1] and str2[j..len2-1] int lcs(string str1 string str2 int len1 int len2  int i int j) {  int &ret = dp[i][j];  // base condition  if (i==len1 || j==len2)  return ret = 0;  // if lcs has been computed  if (ret != -1)  return ret;  ret = 0;  // if characters are same return previous + 1 else  // max of two sequences after removing i'th and j'th  // char one by one  if (str1[i] == str2[j])  ret = 1 + lcs(str1 str2 len1 len2 i+1 j+1);  else  ret = max(lcs(str1 str2 len1 len2 i+1 j)  lcs(str1 str2 len1 len2 i j+1));  return ret; } // Function to print all routes common sub-sequences of // length lcslen void printAll(string str1 string str2 int len1 int len2  char data[] int indx1 int indx2 int currlcs) {  // if currlcs is equal to lcslen then print it  if (currlcs == lcslen)  {  data[currlcs] = '';  puts(data);  return;  }  // if we are done with all the characters of both string  if (indx1==len1 || indx2==len2)  return;  // here we have to print all sub-sequences lexicographically  // that's why we start from 'a'to'z' if this character is  // present in both of them then append it in data[] and same  // remaining part  for (char ch='a'; ch<='z'; ch++)  {  // done is a flag to tell that we have printed all the  // subsequences corresponding to current character  bool done = false;  for (int i=indx1; i<len1; i++)  {  // if character ch is present in str1 then check if  // it is present in str2  if (ch==str1[i])  {  for (int j=indx2; j<len2; j++)  {  // if ch is present in both of them and  // remaining length is equal to remaining  // lcs length then add ch in sub-sequence  if (ch==str2[j] &&  dp[i][j] == lcslen-currlcs)  {  data[currlcs] = ch;  printAll(str1 str2 len1 len2 data i+1 j+1 currlcs+1);  done = true;  break;  }  }  }  // If we found LCS beginning with current character.   if (done)  break;  }  } } // This function prints all LCS of str1 and str2 // in lexicographic order. void prinlAllLCSSorted(string str1 string str2) {  // Find lengths of both strings  int len1 = str1.length() len2 = str2.length();  // Find length of LCS  memset(dp -1 sizeof(dp));  lcslen = lcs(str1 str2 len1 len2 0 0);  // Print all LCS using recursive backtracking  // data[] is used to store individual LCS.  char data[MAX];  printAll(str1 str2 len1 len2 data 0 0 0); } // Driver program to run the case int main() {  string str1 = 'abcabcaa' str2 = 'acbacba';  prinlAllLCSSorted(str1 str2);  return 0; } 

// Java program to find all LCS of two strings in  // sorted order.  import java.io.*; class GFG {  static int MAX = 100;  // length of lcs   static int lcslen = 0;   // dp matrix to store result of sub calls for lcs   static int[][] dp = new int[MAX][MAX];   // A memoization based function that returns LCS of   // str1[i..len1-1] and str2[j..len2-1]   static int lcs(String str1 String str2   int len1 int len2 int i int j)   {   int ret = dp[i][j];   // base condition   if (i == len1 || j == len2)   return ret = 0;   // if lcs has been computed   if (ret != -1)   return ret;   ret = 0;   // if characters are same return previous + 1 else   // max of two sequences after removing i'th and j'th   // char one by one   if (str1.charAt(i) == str2.charAt(j))   ret = 1 + lcs(str1 str2 len1 len2 i + 1 j + 1);   else  ret = Math.max(lcs(str1 str2 len1 len2 i + 1 j)   lcs(str1 str2 len1 len2 i j + 1));   return dp[i][j]=ret;   }   // Function to print all routes common sub-sequences of   // length lcslen   static void printAll(String str1 String str2 int len1 int len2   char[] data int indx1 int indx2 int currlcs)   {   // if currlcs is equal to lcslen then print it   if (currlcs == lcslen)   {   data[currlcs] = '';   System.out.println(new String(data));   return;   }   // if we are done with all the characters of both string   if (indx1 == len1 || indx2 == len2)   return;   // here we have to print all sub-sequences lexicographically   // that's why we start from 'a'to'z' if this character is   // present in both of them then append it in data[] and same   // remaining part   for (char ch ='a'; ch <='z'; ch++)   {   // done is a flag to tell that we have printed all the   // subsequences corresponding to current character   boolean done = false;   for (int i = indx1; i < len1; i++)   {   // if character ch is present in str1 then check if   // it is present in str2   if (ch == str1.charAt(i))   {   for (int j = indx2; j < len2; j++)   {  // if ch is present in both of them and   // remaining length is equal to remaining   // lcs length then add ch in sub-sequence   if (ch == str2.charAt(j) &&   dp[i][j] == lcslen - currlcs)   {   data[currlcs] = ch;   printAll(str1 str2 len1 len2   data i + 1 j + 1 currlcs + 1);   done = true;   break;   }   }   }   // If we found LCS beginning with current character.   if (done)   break;   }   }   }   // This function prints all LCS of str1 and str2   // in lexicographic order.   static void prinlAllLCSSorted(String str1 String str2)   {   // Find lengths of both strings   int len1 = str1.length() len2 = str2.length();   // Find length of LCS   for(int i = 0; i < MAX; i++)  {  for(int j = 0; j < MAX; j++)  {  dp[i][j] = -1;  }  }  lcslen = lcs(str1 str2 len1 len2 0 0);   // Print all LCS using recursive backtracking   // data[] is used to store individual LCS.   char[] data = new char[MAX];   printAll(str1 str2 len1 len2 data 0 0 0);   }   // Driver code  public static void main(String[] args)   {  String str1 = 'abcabcaa' str2 = 'acbacba';   prinlAllLCSSorted(str1 str2);   } } // This code is contributed by divyesh072019 

# Python3 program to find all LCS of two strings in # sorted order. MAX=100 lcslen = 0 # dp matrix to store result of sub calls for lcs dp=[[-1 for i in range(MAX)] for i in range(MAX)] # A memoization based function that returns LCS of # str1[i..len1-1] and str2[j..len2-1] def lcs(str1 str2 len1 len2 i j): # base condition if (i == len1 or j == len2): dp[i][j] = 0 return dp[i][j] # if lcs has been computed if (dp[i][j] != -1): return dp[i][j] ret = 0 # if characters are same return previous + 1 else # max of two sequences after removing i'th and j'th # char one by one if (str1[i] == str2[j]): ret = 1 + lcs(str1 str2 len1 len2 i + 1 j + 1) else: ret = max(lcs(str1 str2 len1 len2 i + 1 j) lcs(str1 str2 len1 len2 i j + 1)) dp[i][j] = ret return ret # Function to print all routes common sub-sequences of # length lcslen def printAll(str1 str2 len1 len2data indx1 indx2 currlcs): # if currlcs is equal to lcslen then print if (currlcs == lcslen): print(''.join(data[:currlcs])) return # if we are done with all the characters of both string if (indx1 == len1 or indx2 == len2): return # here we have to print all sub-sequences lexicographically # that's why we start from 'a'to'z' if this character is # present in both of them then append it in data[] and same # remaining part for ch in range(ord('a')ord('z') + 1): # done is a flag to tell that we have printed all the # subsequences corresponding to current character done = False for i in range(indx1len1): # if character ch is present in str1 then check if # it is present in str2 if (chr(ch)==str1[i]): for j in range(indx2 len2): # if ch is present in both of them and # remaining length is equal to remaining # lcs length then add ch in sub-sequence if (chr(ch) == str2[j] and dp[i][j] == lcslen-currlcs): data[currlcs] = chr(ch) printAll(str1 str2 len1 len2 data i + 1 j + 1 currlcs + 1) done = True break # If we found LCS beginning with current character. if (done): break # This function prints all LCS of str1 and str2 # in lexicographic order. def prinlAllLCSSorted(str1 str2): global lcslen # Find lengths of both strings len1len2 = len(str1)len(str2) lcslen = lcs(str1 str2 len1 len2 0 0) # Print all LCS using recursive backtracking # data[] is used to store individual LCS. data = ['a' for i in range(MAX)] printAll(str1 str2 len1 len2 data 0 0 0) # Driver program to run the case if __name__ == '__main__': str1 = 'abcabcaa' str2 = 'acbacba' prinlAllLCSSorted(str1 str2) # This code is contributed by mohit kumar 29 

// C# program to find all LCS of two strings in  // sorted order.  using System; class GFG  {   static int MAX = 100;    // length of lcs   static int lcslen = 0;     // dp matrix to store result of sub calls for lcs   static int[] dp = new int[MAXMAX];     // A memoization based function that returns LCS of   // str1[i..len1-1] and str2[j..len2-1]   static int lcs(string str1 string str2   int len1 int len2 int i int j)   {   int ret = dp[i j];     // base condition   if (i == len1 || j == len2)   return ret = 0;     // if lcs has been computed   if (ret != -1)   return ret;     ret = 0;     // if characters are same return previous + 1 else   // max of two sequences after removing i'th and j'th   // char one by one   if (str1[i] == str2[j])   ret = 1 + lcs(str1 str2 len1 len2 i + 1 j + 1);   else  ret = Math.Max(lcs(str1 str2 len1 len2 i + 1 j)   lcs(str1 str2 len1 len2 i j + 1));   return ret;   }     // Function to print all routes common sub-sequences of   // length lcslen   static void printAll(string str1 string str2 int len1 int len2   char[] data int indx1 int indx2 int currlcs)   {   // if currlcs is equal to lcslen then print it   if (currlcs == lcslen)   {   data[currlcs] = '';   Console.WriteLine(new string(data));   return;   }     // if we are done with all the characters of both string   if (indx1 == len1 || indx2 == len2)   return;     // here we have to print all sub-sequences lexicographically   // that's why we start from 'a'to'z' if this character is   // present in both of them then append it in data[] and same   // remaining part   for (char ch='a'; ch<='z'; ch++)   {   // done is a flag to tell that we have printed all the   // subsequences corresponding to current character   bool done = false;     for (int i = indx1; i < len1; i++)   {   // if character ch is present in str1 then check if   // it is present in str2   if (ch == str1[i])   {   for (int j = indx2; j < len2; j++)   {   // if ch is present in both of them and   // remaining length is equal to remaining   // lcs length then add ch in sub-sequence   if (ch == str2[j] &&   lcs(str1 str2 len1 len2 i j) == lcslen-currlcs)   {   data[currlcs] = ch;   printAll(str1 str2 len1 len2 data i+1 j+1 currlcs+1);   done = true;   break;   }   }   }     // If we found LCS beginning with current character.   if (done)   break;   }   }   }     // This function prints all LCS of str1 and str2   // in lexicographic order.   static void prinlAllLCSSorted(string str1 string str2)   {   // Find lengths of both strings   int len1 = str1.Length len2 = str2.Length;     // Find length of LCS   for(int i = 0; i < MAX; i++)  {  for(int j = 0; j < MAX; j++)  {  dp[i j] = -1;  }  }  lcslen = lcs(str1 str2 len1 len2 0 0);     // Print all LCS using recursive backtracking   // data[] is used to store individual LCS.   char[] data = new char[MAX];   printAll(str1 str2 len1 len2 data 0 0 0);   }   // Driver code  static void Main()   {  string str1 = 'abcabcaa' str2 = 'acbacba';   prinlAllLCSSorted(str1 str2);   } } // This code is contributed by divyeshrabadiya07 

<script> // Javascript program to find all LCS of two strings in // sorted order.    let MAX = 100;  // length of lcs  let lcslen = 0;    // dp matrix to store result of sub calls for lcs  let dp = new Array(MAX);    // A memoization based function that returns LCS of  // str1[i..len1-1] and str2[j..len2-1]  function lcs(str1str2len1len2ij)  {  let ret = dp[i][j];    // base condition  if (i == len1 || j == len2)  return ret = 0;    // if lcs has been computed  if (ret != -1)  return ret;   ret = 0;    // if characters are same return previous + 1 else  // max of two sequences after removing i'th and j'th  // char one by one  if (str1[i] == str2[j])  ret = 1 + lcs(str1 str2 len1 len2 i + 1 j + 1);  else  ret = Math.max(lcs(str1 str2 len1 len2 i + 1 j)  lcs(str1 str2 len1 len2 i j + 1));  return ret;  }    // Function to print all routes common sub-sequences of  // length lcslen  function printAll(str1str2len1len2dataindx1indx2currlcs)  {  // if currlcs is equal to lcslen then print it  if (currlcs == lcslen)  {  data[currlcs] = null;  document.write(data.join('')+'  
');  return;  }    // if we are done with all the characters of both string  if (indx1 == len1 || indx2 == len2)  return;    // here we have to print all sub-sequences lexicographically  // that's why we start from 'a'to'z' if this character is  // present in both of them then append it in data[] and same  // remaining part  for (let ch ='a'.charCodeAt(0); ch <='z'.charCodeAt(0); ch++)  {    // done is a flag to tell that we have printed all the  // subsequences corresponding to current character  let done = false;    for (let i = indx1; i < len1; i++)  {    // if character ch is present in str1 then check if  // it is present in str2  if (ch == str1[i].charCodeAt(0))  {  for (let j = indx2; j < len2; j++)  {    // if ch is present in both of them and  // remaining length is equal to remaining  // lcs length then add ch in sub-sequence  if (ch == str2[j].charCodeAt(0) &&  lcs(str1 str2 len1 len2 i j) == lcslen - currlcs)  {  data[currlcs] = String.fromCharCode(ch);  printAll(str1 str2 len1 len2  data i + 1 j + 1 currlcs + 1);  done = true;  break;  }  }  }    // If we found LCS beginning with current character.   if (done)  break;  }  }  }    // This function prints all LCS of str1 and str2  // in lexicographic order.  function prinlAllLCSSorted(str1str2)  {  // Find lengths of both strings  let len1 = str1.length len2 = str2.length;    // Find length of LCS  for(let i = 0; i < MAX; i++)  {  dp[i]=new Array(MAX);  for(let j = 0; j < MAX; j++)  {  dp[i][j] = -1;  }  }  lcslen = lcs(str1 str2 len1 len2 0 0);    // Print all LCS using recursive backtracking  // data[] is used to store individual LCS.  let data = new Array(MAX);  printAll(str1 str2 len1 len2 data 0 0 0);  }    // Driver code  let str1 = 'abcabcaa' str2 = 'acbacba';  prinlAllLCSSorted(str1 str2);    // This code is contributed by unknown2108 </script>