Longest Common Subsequence problem: solved

Problem Statement

Assume that S1 and S2 are two strings and that:

S1 = akfdcmejf
S2=”sfkpdcnmej”

The "kdcmej" character is the Longest Common Subsequence (LCS) between these two strings. It's not a given that a subsequence will be contiguous just because it's a subsequence.

Subsequence

Take the sequence S = [s1, s2, s3, s4,..., sn] into consideration.

If and only if it can be derived from the S deletion of some components, a sequence Z = z1, z2, z3, z4,...,zm> over S is a subsequence of S.

Common Subsequence

Let's say that X and Y are sequences spanning a limited number of elements. If Z is a subsequence of both X and Y, then Z is a common subsequence of X andY.

Theory

The longest common subsequence challenge aims to identify a common subsequence of all the given sequences that has the maximum length.

A well-known topic in computer science, the most extended common subsequence problem serves as the foundation for data comparison tools like the diff-utility and has uses in bioinformatics.

Algorithm

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := Length(X)
n := Length(Y)
for i = 1 to m do
C[i, 0] := 0
for j = 1 to n do
C[0, j] := 0
for i = 1 to m do
for j = 1 to n do
if xi = yj
C[i, j] := C[i - 1, j - 1] + 1
B[i, j] := 'D'
else
if C[i - 1, j] ≥ C[i, j - 1]
C[i, j] := C[i - 1, j] + 1
B[i, j] := 'U'
else
C[i, j] := C[i, j - 1] + 1
B[i, j] := 'L'
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0
return
if B[i, j] = 'D'
Print-LCS(B, X, i-1, j-1)
Print(xi)
else if B[i, j] = 'U'
Print-LCS(B, X, i-1, j)
else
Print-LCS(B, X, i, j-1)

Top-Down Approach: Using C++

// Board Infinity
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

// Function to find the length of the longest common subsequence of substring
// `X[0...m-1]` and `Y[0...n-1]`
int LCSLength(string X, string Y, int m, int n, auto &lookup)
{
// return if the end of either string is reached
if (m == 0 || n == 0) {
return 0;
}

// construct a unique map key from dynamic elements of the input
string key = to_string(m) + "|" + to_string(n);

// if the subproblem is seen for the first time, solve it and
// store its result in a map
if (lookup.find(key) == lookup.end())
{
// if the last character of `X` and `Y` matches
if (X[m - 1] == Y[n - 1]) {
lookup[key] = LCSLength(X, Y, m - 1, n - 1, lookup) + 1;
}
else {
// otherwise, if the last character of `X` and `Y` don't match
lookup[key] = max(LCSLength(X, Y, m, n - 1, lookup),
LCSLength(X, Y, m - 1, n, lookup));
}
}

// return the subproblem solution from the map
return lookup[key];
}

int main()
{
string X = "ABCBDAB", Y = "BDCABA";

// create a map to store solutions to subproblems
unordered_map<string, int> lookup;

cout << "The length of the LCS is "
<< LCSLength(X, Y, X.length(), Y.length(), lookup);

return 0;
}

Bottom-up Approach: Using C++

// Board Infinity
#include <iostream>
#include <string>
using namespace std;

// Function to find the length of the longest common subsequence of substring
// `X[0...m-1]` and `Y[0...n-1]`
int LCSLength(string X, string Y)
{
int m = X.length(), n = Y.length();

// lookup table stores solution to already computed subproblems;
// i.e., `lookup[i][j]` stores the length of LCS of substring
// `X[0...i-1]` and `Y[0...j-1]`
int lookup[m + 1][n + 1];

// first column of the lookup table will be all 0s
for (int i = 0; i <= m; i++) {
lookup[i][0] = 0;
}

// first row of the lookup table will be all 0s
for (int j = 0; j <= n; j++) {
lookup[0][j] = 0;
}

// fill the lookup table in a bottom-up manner
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// if the current character of `X` and `Y` matches
if (X[i - 1] == Y[j - 1]) {
lookup[i][j] = lookup[i - 1][j - 1] + 1;
}
// otherwise, if the current character of `X` and `Y` don't match
else {
lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]);
}
}
}

// LCS will be the last entry in the lookup table
return lookup[m][n];
}

int main()
{
string X = "XMJYAUZ", Y = "MZJAWXU";

cout << "The length of the LCS is " << LCSLength(X, Y);

return 0;
}

write your code here: Coding Playground