**Problem :- **

Longest Common Subsequence **( LCS )** problem.

Given two sequences, find the longest common subsequence present in both the sequences.

In **subsequence**, elements of the sequence need not be consecutive.

For e.g, **"lgtm"** is a subsequence of **"algorithms"**.

Consider two sequences **{ 1, 2, 3, 2, 4, 1, 2 }** & **{ 2, 4, 3, 1, 2, 1 }**

Longest Common Subsequence **( LCS )** is **{ 2, 3, 2, 1 }** of length **4**.

**Solution :- **

Suppose we want to find **LCS** of two strings ( **str1** of size **m** and **str2** of size **n** )

First, we will characterize the structure of an optimal solution.

Let **lcs ( i , j )** denotes the length of **LCS** till index **i** of str1 and index **j** of str2.

There are **2** possibilities :

**1 )** if **str1 ( i ) == str2 ( j )** , then the problem reduces to finding **1 + lcs ( i - 1 , j - 1 )**

**2 )** if **str1 ( i ) != str2 ( j )** , then the problem reduces to finding maximum of the two overlapping subproblems

[ **lcs ( i - 1 , j )** and **lcs ( i , j - 1 )** ]

Thus, optimal solution is defined recursively as :

**lcs ( i , j ) = 1 + lcs ( i - 1 , j - 1 ) if str1 ( i ) == str2 ( j )**

**lcs ( i , j ) = max [ lcs ( i - 1 , j ) , lcs ( i , j - 1 ) ] if str1 ( i ) != str2 ( j )**

Now, **lcs ( i , j )** can be found for any values of **i** and **j**.

Eventually, **lcs ( m , n )** gives the required solution.

The implementation shown below maintains some additional information to print the actual Longest Common Subsequence apart
from the length of LCS.

**#include<iostream>**
**using namespace** std;
*// print the Longest common subsequence*
**void** printLCS(**int** **sequence,**int** seq1[],**int** i,**int** j) {
**if**(i == 0 || j == 0)
**return**;
**if**(sequence[i][j] == 1) {
printLCS(sequence,seq1,i-1,j-1);
cout<<"\t"<<seq1[i-1];
}
**else
if**(sequence[i][j] == 2)
printLCS(sequence,seq1,i-1,j);
**else**
printLCS(sequence,seq1,i,j-1);
}
*/* find the longest common subsequence of two strings seq1 & seq2
suppose m -> length of seq1 & n -> length of seq2
lcs(i,j) -> LCS till index 'i' of seq1 and index 'j' of seq2
lcs(m,n) -> LCS if seq1 and seq2
Standard Recursive Solution :-
1) lcs(i,j) = lcs(i-1,j-1)+1, if seq1(i) = seq2(j)
2) lcs(i,j) = max[lcs(i,j-1),lcs(i-1,j)], if seq1(i) != seq2(j)
In the actual implementation, we compare seq[i-1] and seq[j-1]
since the array index starts from 0
*/*
**int** findLCS(**int** seq1[],**int** m,**int** seq2[],**int** n) {
**int** i,j;
*// matrix to hold lcs values*
**int** **lcs;
lcs = **new int***[m+1];
**for** (j=0;j<m+1;j++) {
lcs[j] = **new int**[n+1];
}
*// matrix to trace the actual subsequence*
**int** **sequence;
sequence = **new int***[m+1];
**for** (j=0;j<m+1;j++) {
sequence[j] = **new int**[n+1];
}
*// if one of the sequence is NULL
// lcs = 0 [boundary cases]*
**for** (i=0;i<=m;i++) lcs[i][0]=0;
**for** (j=0;j<=n;j++) lcs[0][j]=0;
*// compute the lcs at each (i,j)
// i -> index of seq1 & j -> index of seq2
// lcs at (m,n) is the final solution
// Values assigned to sequence(i,j) [1/2/3]
// differentiates the three cases as implemented below
// this will be used for tracing the actual LCS*
**for** (i=1;i<=m;i++) {
**for** (j=1;j<=n;j++) {
**if** (seq1[i-1] == seq2[j-1]) {
*// case1 of standard recursive solution*
lcs[i][j] = lcs[i-1][j-1]+1;
sequence[i][j] = 1;
}
*// case2 of standard recursive solution *
**else if** (lcs[i-1][j] >= lcs[i][j-1]) {
lcs[i][j] = lcs[i-1][j];
sequence[i][j] = 2;
}
**else** {
lcs[i][j] = lcs[i][j-1];
sequence[i][j] = 3;
}
}
}
cout<<"\nThe LCS is :-\n";
printLCS(sequence,seq1,m,n);
**return** lcs[m][n];
}
*// main*
**int** main() {
**int** seq1[] = {1,2,3,2,4,1,2};
**int** seq2[] = {2,4,3,1,2,1};
**int** len_seq1 = **sizeof**(seq1)/**sizeof**(seq1[0]);
**int** len_seq2 = **sizeof**(seq2)/**sizeof**(seq2[0]);
**int** len_lcs = findLCS(seq1,len_seq1,seq2,len_seq2);
cout<<"\nLCS length :: "<<len_lcs;
cout<<endl;
**return** 0;
}