3
\$\begingroup\$

I'm relatively new to C++ and am trying to learn good programming practices and habits from the beginning. The code I wrote finds the largest common subsequence between to strings (and output the resulting subsequence, not the length of the subsequence).

I was wondering if there were any improvements I could make to make this more efficient. I know that it is exponential run-time, and there is a more efficient approach via dynamic programming, but I am simply interested in improving this specific algorithm (i.e. the recursive approach). For instance, I know that maybe concatenating my strings via += may be expensive, or maybe there is a way to use references to avoid the copying of strings.

#include <string>
#include <iostream>

// utility function to return the largest (wrt length) of two strings
std::string& max(std::string &s1, std::string &s2)
{
    return s1.size() > s2.size() ? s1 : s2;
}

// Return the lowest common sequence of characters contained in the
// strings s1 and s2 (as a string)
// e.g. lcs("ACBEA", "ADCA") -> "ACA" (string objects, not const char *)
std::string lcs(std::string s1, std::string s2)
{
    // initialize the lcs to be an empty string
    std::string lcsStr;

    if (s1.empty() || s2.empty())
        return std::string(); // empty string constructor

    if (s1.at(s1.size() - 1) == s2.at(s2.size() - 1))
    {
        lcsStr.push_back(s1.at(s1.size() - 1));
        s1.pop_back();
        s2.pop_back();
        return lcs(s1, s2) += lcsStr;
    }

    else
        return max(
            lcs(s1.substr(0, s1.size() - 1), s2), lcs(s1, s2.substr(0, s2.size() - 1))
        ) += lcsStr;
}


int main()
{
    std::cout << "Enter two strings:" << std::endl;
    std::string s1, s2;
    std::cin >> s1 >> s2;

    std::cout << lcs(s1, s2) << std::endl;

    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.