Longest Common Subsequence problem: solved

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)

// 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;
}

// 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;
}