• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Printing Longest Common Subsequence

April 25, 2014 by Dhaval Dave

Printing Longest Common Subsequence

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

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

We have discussed Longest Common Subsequence (LCS) problem in a previous post. The function discussed there was mainly to find the length of LCS. To find length of LCS, a 2D table L[][] was constructed. In this post, the function to construct and print LCS is discussed.

/* Dynamic Programming implementation of LCS problem */
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
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] = ''; // 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;
}

/* Driver program to test above function */
int main()
{
  char X[] = "AGGTAB";
  char Y[] = "GXTXAYB";
  int m = strlen(X);
  int n = strlen(Y);
  lcs(X, Y, m, n);
  return 0;
}

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE

Similar Articles

Filed Under: Amazon Interview Question, Interview Questions, Microsoft Interview Questions, problem Tagged With: 2d matrix, Dynamic Programming, string

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Best Java Book | Top Java Programming Book for Beginners

Find if two rectangles overlap

BFS (Breath First Search)

LeetCode: Container With Most Water

Binary Tree in Java

CodeChef’ RRCOPY

Trie Dictionary

Get K Max and Delete K Max in stream of incoming integers

Print Power Set of a Set

Memory Efficient LinkedList

Implement a generic binary search algorithm for Integer Double String etc

VMWare Openings

DFS (Depth First Search)

Wrong Directions given find minimum moves so that he can reach to the destination

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Find and print longest consecutive number sequence in a given sequence in O(n)

Minimum insertions to form a palindrome

Right view of Binary tree

Hackerearth : Counting Subarrays

Facebook Interview Question : Interleave List

Find next greater number with same set of digits

Number of Islands BFS/DFS

1014 Practice Question of New GRE – Princeton

Diagonal Traversal of Binary Tree

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Python Array String

Max Sum in circularly situated Values

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Convert number to words java

Copyright © 2023 · Genesis Framework · WordPress · Log in