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;
}