Printing Longest Common Subsequence | GeeksforGeeks

Printing Longest Common Subsequence | GeeksforGeeks

Given two sequences, print the longest subsequence present in both of them.

Following is detailed algorithm to print the LCS. It uses the same 2D table L[][].

1) Construct L[m+1][n+1] using the steps discussed in previous post.

2) The value L[m][n] contains length of LCS. Create a character array lcs[] of length equal to the length of lcs plus 1 (one extra to store \0).

2) Traverse the 2D array starting from L[m][n]. Do following for every cell L[i][j]
…..a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
…..b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

void lcs( char *X, char *Y, int m, int n )

{

   int L[m+1][n+1];

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note

      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */

   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]);

     }

   }

   // Following code is used to print LCS

   int index = L[m][n];

   // Create a character array to store the lcs string

   char lcs[index+1];

   lcs[index] = '\0'; // Set the terminating character

   // Start from the right-most-bottom-most corner and

   // one by one store characters in lcs[]

   int i = m, j = n;

   while (i > 0 && j > 0)

   {

      // If current character in X[] and Y are same, then

      // current character is part of LCS

      if (X[i-1] == Y[j-1])

      {

          lcs[index-1] = X[i-1]; // Put current character in result

          i--; j--; index--;     // reduce values of i, j and index

      }

      // If not same, then find the larger of two and

      // go in the direction of larger value

      else if (L[i-1][j] > L[i][j-1])

         i--;

      else

         j--;

   }

   // Print the lcs

   cout << "LCS of " << X << " and " << Y << " is " << lcs;

}

Java Solution
https://www.hackerrank.com/challenges/dynamic-programming-classics-the-longest-common-subsequence
https://codepair.hackerrank.com/paper/ZggdyeVg?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
    private static void findLCS(int[] a, int[] b) {
        int[][] lcs = new int[a.length+1][b.length+1];
        for(int i = 0; i <= a.length; i++) {
          for(int j = 0; j <= b.length; j++) {
              if(i == 0 | j == 0)
                  lcs[i][j] = 0;
              else if(a[i-1] == b[j-1])
                  lcs[i][j] = lcs[i-1][j-1] +1;
              else
                  lcs[i][j] = lcs[i-1][j] > lcs[i][j-1] ? lcs[i-1][j]:lcs[i][j-1];                       }
        }
       
        int[] result = new int[lcs[a.length][b.length]];
        int index = result.length;
        int i = a.length, j = b.length;
        while(i > 0 && j > 0) {
           if(a[i-1] == b[j-1]) {
               result[index-1] = a[i-1];
               index--; i--; j--;
           } else {
               if(lcs[i-1][j] > lcs[i][j-1]) {
                   i--;
               } else {
                   j--;
               }
           }
        }
        for(int x:result)
            System.out.print(x + " ");    
    }

Read full article from Printing Longest Common Subsequence | GeeksforGeeks