fbpx

C++: Longest Common Subsequence

Bjarne-stroustrup
 

#include <algorithm>
#include <string>
#include <vector>

#include <stdio.h>
#include <string.h>

// See http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node4.html.
class LCS
{
	class LCSTable
	{
		size_t   m_;
		size_t   n_;
		size_t*  data_;
	public:
		LCSTable(size_t m, size_t n)
		: m_(m)
		, n_(n)
		{
			data_ = new size_t[(m_ + 1) * (n_ + 1)];
		}
		~LCSTable()
		{
			delete [] data_;
		}

		void setAt(size_t i, size_t j, size_t value)
		{
			data_[i + j * (m_ + 1)] = value;
		}

		size_t getAt(size_t i, size_t j) const
		{
			return data_[i + j * (m_ + 1)];
		}

		template<typename T> void
		build(const T* X, const T* Y)
		{
			for (size_t i=0; i<=m_; ++i)
			setAt(i, 0, 0);

			for (size_t j=0; j<=n_; ++j)
			setAt(0, j, 0);

			for (size_t i = 0; i < m_; ++i)
			{
				for (size_t j = 0; j < n_; ++j)
				{
					if (X[i] == Y[j])
					setAt(i+1, j+1, getAt(i, j)+1);
					else
					setAt(i+1, j+1, std::max(getAt(i+1, j), getAt(i, j+1)));
				}
			}
		}
	};

	template<typename T> static void
	backtrackOne(const LCSTable& table,
	const T* X, const T* Y, size_t i, size_t j,
	std::vector<T>& result)
	{
		if (i == 0 || j == 0)
		return;
		if (X[i - 1] == Y[j - 1])
		{
			backtrackOne(table, X, Y, i - 1, j - 1, result);
			result.push_back(X[i - 1]);
			return;
		}
		if (table.getAt(i, j - 1) > table.getAt(i -1, j))
		backtrackOne(table, X, Y, i, j - 1, result);
		else
		backtrackOne(table, X, Y, i - 1, j, result);
	}

public:
	template<typename T> static void
	findOne(T* X, size_t m, T* Y, size_t n,
	std::vector<T>& result)
	{
		LCSTable table(m, n);
		table.build(X, Y);
		backtrackOne(table, X, Y, m, n, result);
	}
};

Usage:

char X[] = "XMJYAUZ";
char Y[] = "MZJAWXU";
std::vector<char> result;
 
LCS::findOne(X, strlen(X), Y, strlen(Y), result);
std::string resultString(&result.front(), result.size());

SOURCE

Our team found a curious site for our readers that are fans of online gaming, a rather exciting site that provides the latest gaming technology. Casinodots.com is the site, they compile the best reviews of MGA casino utan svensk licens sites. This site might pique your curiosity and you can win extra money!