# 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.

``````#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;
char Y;
cin>>X>>Y;
int m = strlen(X);
int n = strlen(Y);
lcs(X, Y, m, n);
return 0;
}``````  