# Largest common subsequence algorithm in C++

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