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

Subscribe to TFE Times

Enter your email address to become a member of TFE Times today!