Hide
Meet people who work on similar things as you – get help if you need it Join Siafoo Now or Learn More

recursive solution for LCS problem Atom Feed 0

In Brief This recursive routine costs a lot and you can see clearly that the cost will be high in terms of repeated comparisons and memory consumption.
# 's
 1#include <iostream>
2#include <string>
3#include <cstdlib>
4
5int lcs( const std::string& s1, const std::string& s2, std::string& result ) {
6 int retval(0);
7 if ( s2.size() > 1 && s1.size() > 1 ) {
8 if ( s1[0] == s2[0] ) {
9 std::string ret1;
10 retval = 1 + lcs(s1.substr(1, s1.size()-1), s2.substr(1,s2.size()-1),ret1);
11 result += s1[0] + ret1;
12 } else {
13 ++i;
14 std::string ret1, ret2;
15 retval = std::max(lcs(s1.substr(1, s1.size()-1), s2,ret1), lcs(s1, s2.substr(1,s2.size()-1),ret2));
16 //std::cout << "ret1 and ret2: " << ret1 << " " << ret2 << std::endl;
17 if (ret1.size() > ret2.size()) result += ret1;
18 else result += ret2;
19 }
20 } else if ( s1.size() && s2.size() && s1[0] == s2[0] ) {
21 result += s1[0];
22 retval = 1;
23 }
24 return retval;
25}
26
27int main (int argc, char * const argv[]) {
28 std::cout << "The purpose is to find the longest and NOT all of the "
29 "actual subsequences. This algorithm is a brute force algorithm to "
30 "demonstrate finding the longest common subsequence." << std::endl
31 << std::endl
32 << "First we proceed by going through X compared to Y and then "
33 "going through comparing Y to X. In either case we get 'a' not 'the' "
34 "longest subsequence." << std::endl << std::endl;
35 std::string x="ABCDBAGZCDCA";
36 std::string y="BCADCGZ";
37 std::string result;
38 std::cout << lcs(x,y,result) << std::endl;
39 std::cout << result << std::endl;
40 result.clear();
41 std::cout << lcs(y,x,result) << std::endl;
42 std::cout << result << std::endl;
43
44 return 0;
45}

This recursive routine costs a lot and you can see clearly that the cost will be high in terms of repeated comparisons and memory consumption.