Algorithm
Article
Library
Snippet
Blog
Group
Users
Forum
Stay up to date – embedded code automagically updates, each snippet and article has a feed
Join Siafoo Now
or
Learn More
brute force example for LCS
Revision 1 vs. Revision 2
Legend:
- Unmodified
- Added
- Removed
-
Code
r1 r2 11 11 << "First we proceed by going through X compared to Y and then " 12 12 "going through comparing Y to X. In either case we get 'a' not 'the' " 13 13 "longest subsequence." << std::endl << std::endl; 14 14 std::vector<std::string> vs; 15 15 std::string x="ABCDBAGZCDCA"; 16 std::string y="BCADCGZ"; 16 //std::string y="BCADCGZ"; 17 std::string y="bcadcgz"; 18 //std::string x="ABCDE"; 19 //std::string y="abcde"; 17 20 size_t n=x.size(); 18 21 size_t m=y.size(); 19 22 size_t i(0), j(0), ii(0), jj(0); 20 23 std::string ts; 21 24 std::string longest; 25 size_t count=0; 22 26 for (; i < n; ++i ) { 23 27 ii = i; 24 28 j = 0; 25 29 jj = j; 26 30 ts.clear(); 27 31 do { 32 count++; 28 33 if (x[ii] == y[j]) { 29 34 std::cout << x[ii]; 30 35 ts += x[ii]; 36 if ( ii == n-1 && j == 0) break; 31 37 ++ii; 32 38 jj=++j; 33 39 } else if ( ++j == m ) { 34 40 j = jj; 35 41 // wasn't found so next in X 36 42 ++ii; 43 if ( j == 0 && ii == n ) break; 37 44 } 38 45 39 46 } while ( ii < n && jj < m ); 40 47 std::cout << std::endl; 41 48 if (ts.size() > longest.size()) longest = ts; 42 49 vs.push_back(ts); 50 if ( j == 0 && ii >= n-1 ) break; 43 51 } 52 std::cout << "Actual number of comparisons/looping: " << count << std::endl << std::endl; 44 53 std::cout << "Longest is: " << longest << std::endl << std::endl; 45 54 std::cout << std::endl << "Going the other way!" << std::endl; 46 55 j=0; 47 56 i=0; 48 57 jj=0; 49 58 ii=0; 50 59 longest.clear(); 60 count=0; 51 61 for (; i < m; ++i ) { 52 62 ii = i; 53 63 j = 0; 54 64 jj = j; 55 65 ts.clear(); 56 66 do { 67 count++; 57 68 if (y[ii] == x[j]) { 58 69 std::cout << y[ii]; 59 70 ts+=y[ii]; 71 if ( ii == n-1 && j == 0) break; 60 72 ++ii; 61 73 jj=++j; 62 74 } else if ( ++j == n ) { 63 75 j = jj; 64 76 // wasn't found so next in Y 65 77 ++ii; 78 if ( j == 0 && ii == n) break; 66 79 } 67 80 68 81 } while ( ii < m && jj < n ); 69 82 std::cout << std::endl; 70 83 vs.push_back(ts); 71 84 if (ts.size() > longest.size()) longest = ts; 85 if ( j == 0 && ii >= n-1 ) break; 72 86 } 87 std::cout << "Actual number of comparisons/looping: " << count << std::endl << std::endl; 73 88 std::cout << "Longest is: " << longest << std::endl << std::endl; 74 89 std::cout << " O(n*m) = O(" << n*m << ")" << std::endl; 75 90 std::cout << "UNIQUE SORTED ORDER: " << std::endl; 76 91 77 92 std::sort(vs.begin(), vs.end()); 78 93 std::vector<std::string>::iterator it = std::unique_copy (vs.begin(), vs.end(), vs.begin()); 79 94 vs.resize(it - vs.begin());