Need a quick chart or graph for your blog? Try our reStructured Text renderer.
Join Siafoo Now
or
Learn More

# recursive solution for LCS problem 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. |

Language | C++ |

# '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.

Add a Comment