[05 Feb 2020] Printing Longest Common Subsequence


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.
/* 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] = '\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;
}
  
/* 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;
}
# Dynamic programming implementation of LCS problem
  
# Returns length of LCS for X[0..m-1], Y[0..n-1] 
def lcs(X, Y, m, n):
    L = [[0 for x in xrange(n+1)] for x in xrange(m+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 i in xrange(m+1):
        for j in xrange(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif 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
    index = L[m][n]
  
    # Create a character array to store the lcs string
    lcs = [""] * (index+1)
    lcs[index] = ""
  
    # Start from the right-most-bottom-most corner and
    # one by one store characters in lcs[]
    i = m
    j = n
    while i > 0 and 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]
            i-=1
            j-=1
            index-=1
  
        # If not same, then find the larger of two and
        # go in the direction of larger value
        elif L[i-1][j] > L[i][j-1]:
            i-=1
        else:
            j-=1
  
    print "LCS of " + X + " and " + Y + " is " + "".join(lcs) 
  
# Driver program
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
lcs(X, Y, m, n)
  
# This code is contributed by BHAVYA JAIN

Output:
LCS of AGGTAB and GXTXAYB is GTAB


















































































Comments

Post a Comment

Popular posts from this blog

Kth most frequent Character in a given String

  Given a string   str   and an integer  K , the task is to find the K-th most frequent character in the string. If there are multiple characters that can account as K-th most frequent character then, print any one of them. Examples: Input:  str = “GeeksforGeeks”, K = 3 Output:  f Explanation: K = 3, here ‘e’ appears 4 times & ‘g’, ‘k’, ‘s’ appears 2 times & ‘o’, ‘f’, ‘r’ appears 1 time. Any output from ‘o’ (or) ‘f’ (or) ‘r’ will be correct. Input:  str = “trichotillomania”, K = 2 Output:  l The idea is to Use the Characters as key in  Hashmap  and store their  occurrences in the string . Sort the Hashmap  and find the K-th character. Below is the implementation of the above approach. // C++ program to find kth most frequent // character in a string #include <bits/stdc++.h> using namespace std;     // Used for sorting by frequency. bool sortByVal( const pair< char , int >& a,                 const pair< char , int >& b) {      return a.second >
Read more

[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples : Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 In the given array all element appear three times except 2 which appears once. Input: arr[] = {10, 20, 10, 30, 10, 30, 30} Output: 20 In the given array all element appear three times except 20 which appears once. Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of
Read more

[17 Feb 2020] Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.

Find the nearest smaller numbers on left side in an array Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side. Examples: Input:  arr[] = {1, 6, 4, 10, 2, 5} Output:         {_, 1, 1,  4, 1, 2} First element ('1') has no element on left side. For 6, there is only one smaller element on left side '1'. For 10, there are three smaller elements on left side (1, 6 and 4), nearest among the three elements is 4. Input: arr[] = {1, 3, 0, 2, 5} Output:        {_, 1, _, 0, 2} Expected time complexity is O(n). // C++ implementation of efficient algorithm to find // smaller element on left side #include <iostream> #include <stack> using namespace std;   // Prints smaller elements on left side of every element void printPrevSmaller(int arr[], int n) {     // Create an empty stack     stack<int> S;       // Traverse all array elements     for (int i=0; i<n; i++)  
Read more