how to save string in longest common subsequence recursive algorithm

Question

I'm trying to implement a naive approach of the longest common subsequence algorithm. I'm using a recursive approach, passing two strings into the function lcs. I successfully counted the number of characters in the longest subsequence.

My problem is printing the characters of the lcs. I thought I could do this by storing matched characters in a string called sub and passing it as a parameter. However, I'm stuck on how to save the string. I've always struggled with recursion, and would appreciate any tips on approaching this problem the right way.

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

juvian juvian · Accepted Answer · 2018-04-26T20:15:52

Be careful, your base case is wrong as you never check a[0] against b[0]. Also, passing string copies is very expensive, much faster to pass just the indexes and work with that. We need to keep track of what characters we matched when a[idxa] == b[idxb]. Here is a solution using vectors:

#include <iostream>
#include <string>
#include <queue>
#include <math.h>
#include <algorithm>    // std::reverse

using namespace std;

string s1, s2;

int lcs(int idx1, int idx2, vector<char> &v){

    if (idx1 == -1 || idx2 == -1){
        return 0;
    }

    if (s1[idx1] == s2[idx2]) {
        v.push_back(s1[idx1]); // record that we used this char
        return 1 + lcs(idx1 - 1, idx2 - 1, v);
    } else {
        vector<char> v1, v2;

        int p1 = lcs(idx1 - 1, idx2, v1); 
        int p2 = lcs(idx1, idx2 - 1, v2);

        if (p1 > p2) { // we used the chars we already had in v + the ones in v1
            v.insert(v.end(), v1.begin(), v1.end());
            return p1;
        } else { // we used the chars we already had in v + the ones in v2
            v.insert(v.end(), v2.begin(), v2.end());
            return p2;
        }
    }
}

int main(int argc, const char * argv[])
{

    s1 = "sdmc";
    s2 = "msdc";

    vector<char> v; // chars we used
    int sol = lcs(s1.length() - 1, s2.length() - 1, v); //i want to output "sdc"
    cout << sol << " ";
    reverse(v.begin(), v.end());

    for (auto num : v) {
        cout << num;
    }

    return 0;
}

how to save string in longest common subsequence recursive algorithm

1 Answers