Longest Common Subsequence


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.


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;
         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])
     cout << "The Longest Common Subsequence is AAB" ;
   cout << "The Longest Common Subsequence is " <<  lcs;

int main()
  char X[10];
  char Y[10];
  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.