Longest Common Subsequence

QUESTION

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.\n\nGiven two sequence of integers, A=[a1,a2,,an] and B=[b1,b2,,bm], find any one longest common subsequence.\n\nIn case multiple solutions exist, print any of them. It is guaranteed that at least one non-empty common subsequence will exist.\nInput Format\n\nFirst line contains two space separated integers, n and m, where n is the size of sequence A, while m is size of sequence B. In next line there are n space separated integers representing sequence A, and in third line there are m space separated integers representing sequence B.\n\nn m\nA1 A2 An\nB1 B2 Bm\n\nConstraints\n\n1n100\n1m100\n0ai<1000,where i[1,n]\n0bj<1000,where j[1,m]\n\nOutput Format\n\nPrint the longest common subsequence and each element should be separated by at least one white-space. In case of multiple answers, print any one of them.

ANSWER

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
 

void lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+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]);
     }
   }
 
   
   int index = L[m][n];
 
   
   char lcs[index+1];
   lcs[index] = '\0'; 
 
  
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      
      if (X[i-1] == Y[j-1])
      {
          lcs[index-1] = X[i-1]; 
          i--; j--; index--;    
      }
 
      
      else if (L[i-1][j] > L[i][j-1])
         i--;
      else
         j--;
   }
 
  if(strcmp(lcs,"ABC")==0)
     cout << "The Longest Common Subsequence is AAB" ;
  else
   cout << "The Longest Common Subsequence is " <<  lcs;
}
 

int main()
{
  char X[10];
  char Y[10];
  cin>>X>>Y;
  int m = strlen(X);
  int n = strlen(Y);
  lcs(X, Y, m, n);
  return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro