License MIT license
Lines 98
Keywords
algorithm (8) c++ (3) LCS (2) longest common subsequence (7)
Permissions
Owner: Michael Case
Viewable by Everyone
Editable by Michael Case
Hide
Siafoo is here to make coding less frustrating and to save you time. Join Siafoo Now or Learn More

find ALL common subsequences and then sort for longest Atom Feed 0

In Brief This one finds all subsequences by proceeding through all possible subsequences. It costs way to much in processing time because of its thoroughness.
# 's
 1#include <iostream>
2#include <algorithm>
3#include <vector>
4#include <string>
5
6int main (int argc, char * const argv[]) {
7 std::cout << "The purpose is to find the longest and NOT all of the "
8 "actual subsequences. This algorithm is a brute force algorithm to "
9 "demonstrate finding the longest common subsequence." << std::endl
10 << std::endl
11 << "First we proceed by going through X compared to Y and then "
12 "going through comparing Y to X. In either case we get 'a' not 'the' "
13 "longest subsequence." << std::endl << std::endl;
14 std::vector<std::string> vs;
15 std::string x="ABCDBAGZCDCA";
16 std::string y="BCADCGZ";
17 //std::string y="bcadcgz";
18 //std::string x="ABCDE";
19 //std::string y="abcde";
20 size_t n=x.size();
21 size_t m=y.size();
22 size_t i(0), j(0), ii(0), jj(0);
23 std::string ts;
24 std::string longest;
25 size_t count=0;
26 for (; i < n; ++i ) {
27 ii = i;
28 j = 0;
29 jj = j;
30 ts.clear();
31 do {
32 count++;
33 if (x[ii] == y[j]) {
34 std::cout << x[ii];
35 ts += x[ii];
36 if ( ii == n-1 && j == 0) break;
37 ++ii;
38 jj=++j;
39 } else if ( ++j == m ) {
40 j = jj;
41 // wasn't found so next in X
42 ++ii;
43 if ( j == 0 && ii == n ) break;
44 }
45
46 } while ( ii < n && jj < m );
47 std::cout << std::endl;
48 if (ts.size() > longest.size()) longest = ts;
49 vs.push_back(ts);
50 if ( j == 0 && ii >= n-1 ) break;
51 }
52 std::cout << "Actual number of comparisons/looping: " << count << std::endl << std::endl;
53 std::cout << "Longest is: " << longest << std::endl << std::endl;
54 std::cout << std::endl << "Going the other way!" << std::endl;
55 j=0;
56 i=0;
57 jj=0;
58 ii=0;
59 longest.clear();
60 count=0;
61 for (; i < m; ++i ) {
62 ii = i;
63 j = 0;
64 jj = j;
65 ts.clear();
66 do {
67 count++;
68 if (y[ii] == x[j]) {
69 std::cout << y[ii];
70 ts+=y[ii];
71 if ( ii == n-1 && j == 0) break;
72 ++ii;
73 jj=++j;
74 } else if ( ++j == n ) {
75 j = jj;
76 // wasn't found so next in Y
77 ++ii;
78 if ( j == 0 && ii == n) break;
79 }
80
81 } while ( ii < m && jj < n );
82 std::cout << std::endl;
83 vs.push_back(ts);
84 if (ts.size() > longest.size()) longest = ts;
85 if ( j == 0 && ii >= n-1 ) break;
86 }
87 std::cout << "Actual number of comparisons/looping: " << count << std::endl << std::endl;
88 std::cout << "Longest is: " << longest << std::endl << std::endl;
89 std::cout << " O(n*m) = O(" << n*m << ")" << std::endl;
90 std::cout << "UNIQUE SORTED ORDER: " << std::endl;
91
92 std::sort(vs.begin(), vs.end());
93 std::vector<std::string>::iterator it = std::unique_copy (vs.begin(), vs.end(), vs.begin());
94 vs.resize(it - vs.begin());
95 for (i=0;i<vs.size();++i) {
96 std::cout << vs[i] << std::endl;
97 }
98 return 0;
99}

This one finds all subsequences by proceeding through all possible subsequences. It costs way to much in processing time because of its thoroughness.