 License MIT license
 Lines 98
##### Keywords algorithm (8) c++ (3) LCS (2)
##### Related recursive solution for LCS problem 'A' Longest Common Subsequence (LCS) implementation LCS C++ template classes LCS Quick Sort
##### Permissions Owner: Michael Case Viewable by Everyone Editable by Michael Case Solve a problem – Filter by language, license, keyword, owner, or search text to find code & info fast.

# find ALL common subsequences and then sort for longest 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.
 Language C++
# '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::endl10	<< std::endl11	<< "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 X42				++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 Y77				++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.