Hide
Free your code from a slow death on your hard drive Join Siafoo Now or Learn More

brute force example for LCS Atom Feed 0

In Brief In this particular example the number of loops is output along with the value of O(n*m). This algorithm is less than perfect; but as far as I can tell, does the job of finding the LCS.
# '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}

In this particular example the number of loops is output along with the value of O(n*m). This algorithm is less than perfect; but as far as I can tell, does the job of finding the LCS.