# The Longest Common Subsequence

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

Given two sequence of integers, A=[a1,a2,…,an] and B=[b1,b2,…,bm], find any one longest common subsequence.

In case multiple solutions exist, print any of them. It is guaranteed that at least one non-empty common subsequence will exist.
Input Format

First 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 m
A1 A2 … An
B1 B2 … Bm

Constraints

1≤n≤100
1≤m≤100
0≤ai<1000,where i∈[1,n]
0≤bj<1000,where j∈[1,m]

Output Format

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

Sample Input

5 6
1 2 3 4 1
3 4 1 2 1 3

Sample Output

1 2 3

Explanation

There is no common subsequence with length larger than 3. And “1 2 3”, “1 2 1”, “3 4 1” are all correct answers.

Tested by Khongor

Suggest Edits

Solved score: 49.50pts
1433 hackers have submitted code

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void lcs(int N,int M,int m[],int n[])
{
int L[M+1][N+1],i,j,k;
for(i=0;i<=M;i++)
{
for(j=0;j<=N;j++)
{
if(i==0 || j==0)
L[i][j]=0;
else if(m[i-1]==n[j-1])
L[i][j]=1+L[i-1][j-1];
else
{
if(L[i-1][j]>L[i][j-1])
{
L[i][j]=L[i-1][j];
}
else
{
L[i][j]=L[i][j-1];
}
}
}
}
k=L[M][N];
int l[k];
i=M;j=N;
while(i>0&&j>0)
{
if(m[i-1]==n[j-1])
{
// printf("%d ",m[i-1]);
l[k-1]=m[i-1];
i--;j--;k--;
}
else if(L[i-1][j]>L[i][j-1])
i--;
else
j--;
}
for(i=0;i<L[M][N];i++)
printf("%d ",l[i]);
printf("\n");
}
int main() {

int N,M,m[100],n[100];
int i,j;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%d",&n[i]);
for(i=0;i<M;i++)
scanf("%d",&m[i]);
lcs(N,M,n,m);
return 0;
}```

Compiled :
http://ideone.com/F2Rgoy