#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int lcs(string a, string b,string sub){
    int aLen = a.length();
    int bLen = b.length();
    if (aLen==0 || bLen==0){
        return 0;
    }
    if(a.at(aLen-1)==b.at(bLen-1)){
        return 1+lcs(a.substr(0,aLen-1),b.substr(0,bLen-1),a.at(aLen-1)+sub); // add letter to subsequence
    }
    else {
        return max(lcs(a.substr(0,aLen-1),b.substr(0,bLen),sub),lcs(a.substr(0,aLen),b.substr(0,bLen-1),sub));
    }
}

int main(int argc, const char * argv[])
{
    char sub[]="";
    int charsInLCS = lcs("sdmc","msdc",sub); //i want to output "sdc"
    cout << charsInLCS << endl;
    return 0;
}