lcsm.cpp

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;

static unordered_map<string, int> lookup;
 
// Function to find the length of the longest common subsequence of
// array `X[0…m-1]` and `Y[0…n-1]`
int lcs2(char  *X, char *Y, int m, int n)
{
    // return if the end of either array 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())
    {
 cout << key << "is not found\n";
     // if the last element of `X` and `Y` matches
        if (X[m - 1] == Y[n - 1]) {
            lookup[key] = lcs2(X, Y, m - 1, n - 1) + 1;
        }
        else {
            // otherwise, if the last element of `X` and `Y` don't match
            lookup[key] = max(lcs2(X, Y, m, n - 1), lcs2(X, Y, m - 1, n));
        }
    } else {
     
     cout << key << "is found \n";
     
    }
    // return the subproblem solution from the map
    return lookup[key];
}
 int lcs2(char *X, char *Y){return lcs2(X,Y, strlen(X), strlen(Y));
                           }

main.cpp

int lcs2(char  *X, char *Y, int m, int n);
int lcs2(char  *X, char *Y);

#include <iostream>
using namespace std;
int main(){

cout << lcs2("asdas","sdas");
cout << lcs2("asdas","das");



}