 # 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] := 0for j = 1 to n do C[0, j] := 0for 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 #include #include 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 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 #include 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;    }     // first row of the lookup table will be all 0s    for (int j = 0; j <= n; j++) {        lookup[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
ProgrammingComputer ScienceCompetitive ProgrammingC++

### Blog | Board Infinity

At Board Infinity we have authors leading in their profession sharing their insights, ideas and inspiration. Here influential thinkers, creators, makers and doers are found in one place.