longestCommonSubsequence.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

map<pair<string, string>, int> memo;
int longestCommonSubsequence(string s, string t) {
    if (s.size() == 0 || t.size() == 0) { return 0; }

    if (memo.find(make_pair(s, t)) != memo.end()) {
        return memo[make_pair(s, t)];
    }

    string s1 = s.substr(0, s.size() - 1);
    string t1 = t.substr(0, t.size() - 1);
    if (s[s.size() - 1] == t[t.size() - 1]) {
        return memo[make_pair(s, t)] = longestCommonSubsequence(s1, t1) + 1;
    }
    else {
        return memo[make_pair(s, t)] = max(longestCommonSubsequence(s1, t), longestCommonSubsequence(s, t1));
    }

}

int main(int argc, char *argv[]) {
    string s = "abcde", t = "aobpc";
    cout << longestCommonSubsequence(s, t) << endl;

    return 0;
}