/*
 * =====================================================================================
 *
 *       Filename:  lcs.hpp
 *
 *    Description:  A class of longest common subsequence (lcs) by dynamic programming
 *
 *        Version:  1.2
 *        Created:  2011年01月03日 20時15分32秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Dirk Chang (), [email protected]
 *        Company:  lc.asiahope.net
 *
 * =====================================================================================
 */
#ifndef LCS_HPP_
#define LCS_HPP_

#include <vector>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <iterator>
#include <algorithm>

struct Default_LCS_Comparison {
	template <typename T>
	static bool equal(T const &x, T const &y) {
		return x == y; // use operator == as the default comparison funtion
	}
};

template <typename COMP = Default_LCS_Comparison>
class LCS {
private:
	enum Direction { NIL = 0, LEFT, UPLEFT, UP };
	typedef size_t IndexType;
	typedef IndexType* Row;
	typedef std::vector<Row> Table;
	typedef std::vector<Direction*> AnsTable;

public:
	LCS(size_t const & reserved = 32) : _length(0), _m(0), _n(0), _reserved(reserved+1) {
		construct_table();
	}
	~LCS() {
		destory_table();
	}
	LCS(LCS const &l) : _length(l._length), _reserved(l._reserved) {
		construct_table();
		for(size_t i = 0; i < _reserved; ++i) {
			std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
			std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
		}
	}
	LCS const &operator=(LCS const &l) {
		_length = l._length;
		_reserved = l._reserved;
		destory_table();
		construct_table();
		for(size_t i = 0; i < _reserved; ++i) {
			std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
			std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
		}
	}

	template<typename const_iterator>
	inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
		_length = 0;
		_m = x_size;
		_n = y_size;

		size_t tmp_max = y_size;
		if(tmp_max < x_size) tmp_max = x_size;
		if(tmp_max >= _reserved) {
			_reserved = tmp_max + 1;
			destory_table();
			construct_table();
		}

		const_iterator xi, yj;
		xi = x_begin;
		size_t i(1), j(1);
		for(i = 1; i <= x_size; ++i) {
			yj = y_begin;
			for(j = 1; j <= y_size; ++j) {
				if(COMP::equal(*xi,*yj)) {
					_compute_table[i][j] = _compute_table[i - 1][j - 1] + 1;
					_answer_table[i][j] = UPLEFT;
				}
				else if(_compute_table[i - 1][j] >= _compute_table[i][j - 1]) {
					_compute_table[i][j] = _compute_table[i - 1][j];
					_answer_table[i][j] = UP;
				}
				else {
					_compute_table[i][j] = _compute_table[i][j - 1];
					_answer_table[i][j] = LEFT;
				}
				++yj;
			}
			++xi;
		}
		_length = _compute_table[x_size][y_size];
		return _length;
	}

	inline IndexType Length() {
		return _length;
	}

	template<typename SEQ, typename ANS>
	int Answer(const SEQ &x, ANS &answer) {
		construct_answer(x, _m, _n, answer);
		return 0;
	}

	void PrintComputeTable(std::ostream &out, int const tab = 2);
	void PrintAnswerTable(std::ostream &out, int const tab = 2);

private:
	template<typename SEQ, typename ANS>
	void construct_answer(const SEQ &x, int const i, int const j, ANS &answer) {
		if(i == 0 || j == 0) return;
		if(_answer_table[i][j] == UPLEFT) {
			construct_answer(x, i - 1, j - 1, answer);
			answer.push_back(x[i - 1]);
		}
		else if(_answer_table[i][j] == UP) {
			construct_answer(x, i - 1, j, answer);
		}
		else construct_answer(x, i, j - 1, answer);
	}

	void construct_table() {
		_compute_table.resize(_reserved, 0);
		_answer_table.resize(_reserved, 0);
		for(size_t i = 0; i < _reserved; ++i) {
			_compute_table[i] = new IndexType [_reserved];
			_answer_table[i] = new Direction [_reserved];
			_compute_table[i][0] = 0;
			_answer_table[i][0] = NIL;
		}
		for(size_t i = 0; i < _reserved; ++i) {
			_compute_table[0][i] = 0;
			_answer_table[0][i] = NIL;
		}
	}
	void destory_table() {
		for(size_t i = 0; i < _reserved; ++i) {
			delete [] _compute_table[i];
			delete [] _answer_table[i];
		}
	}

private:
	Table _compute_table;
	AnsTable _answer_table;
	IndexType _length, _m, _n;
	size_t _reserved;
};

template <typename COMP>
void LCS<COMP>::PrintAnswerTable(std::ostream &out, int const tab) {
	int i, j;
	out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
	for(i = 0; i < _n; ++i) {
		out << std::setw(tab) << i;
	}
	out << '\n';

	out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
	out << std::setw(tab) << '0' << std::setw(tab) << 'x';
	for(i = 0; i< _n; ++i) {
		out << std::setw(tab) << '0';
	}
	out << '\n';

	for(i = 1; i < _m; ++i) {
		out << std::setw(tab) << i << std::setw(tab) << ' ';
		for(j = 0; j < _n; ++j) {
			out << std::setw(tab) << _answer_table[i][j];
		}
		out << '\n';
	}
	out << '\n';
}


template <typename COMP>
void LCS<COMP>::PrintComputeTable(std::ostream &out, int const tab) {
	int i, j;
	out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
	for(i = 0; i < _n; ++i) {
		out << std::setw(tab) << i;
	}
	out << '\n';

	out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
	out << std::setw(tab) << '0' << std::setw(tab) << 'x';
	for(i = 0; i< _n; ++i) {
		out << std::setw(tab) << '0';
	}
	out << '\n';

	for(i = 1; i < _m; ++i) {
		out << std::setw(tab) << i << std::setw(tab) << ' ';
		for(j = 0; j < _n; ++j) {
			out << std::setw(tab) << _compute_table[i][j];
		}
		out << '\n';
	}
	out << '\n';
}

template <typename COMP = Default_LCS_Comparison>
class LCS_NOANS {
private:
	typedef size_t IndexType;
	typedef IndexType* Row;
	typedef std::vector<Row> Table;

public:
	LCS_NOANS(size_t const & reserved = 32) : _length(-1), _reserved(reserved+1) {
		_compute_table.resize(2, 0);
		_compute_table[0] = new IndexType [_reserved];
		_compute_table[1] = new IndexType [_reserved];
	}
	~LCS_NOANS() {
		delete [] _compute_table[0];
		delete [] _compute_table[1];
	}
	LCS_NOANS(LCS_NOANS const &l) : _length(l._length), _reserved(l._reserved) {
		_compute_table[0] = new IndexType [_reserved];
		_compute_table[1] = new IndexType [_reserved];
		std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
		std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
	}
	LCS_NOANS const &operator=(LCS_NOANS const &l) {
		_length = l._length;
		_reserved = l._reserved;
		delete [] _compute_table[0];
		delete [] _compute_table[1];
		_compute_table[0] = new IndexType [_reserved];
		_compute_table[1] = new IndexType [_reserved];
		std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
		std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
	}

	template<typename const_iterator>
	inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
		_length = 0;

		size_t tmp_max = y_size;
		if(tmp_max < x_size) tmp_max = x_size;
		if(tmp_max >= _reserved) {
			_reserved = tmp_max + 1;
			delete [] _compute_table[0];
			delete [] _compute_table[1];
			_compute_table[0] = new IndexType [_reserved];
			_compute_table[1] = new IndexType [_reserved];
		}
		std::memset(_compute_table[0], 0, sizeof(IndexType)*_reserved);
		_compute_table[1][0] = 0;

		const_iterator xi, yj;
		xi = x_begin;
		size_t i(1), j(1);
		for(i = 1; i <= x_size; ++i) {
			yj = y_begin;
			_compute_table[i%2][0] = 0;
			for(j = 1; j <= y_size; ++j) {
				if(i%2) {
					if(COMP::equal(*xi,*yj)) {
						//std::cout << "(" << *xi << "," << *yj << ")";
						_compute_table[1][j] = _compute_table[0][j - 1] + 1;
					}
					else if(_compute_table[0][j] >= _compute_table[1][j - 1]) {
						_compute_table[1][j] = _compute_table[0][j];
					}
					else {
						_compute_table[1][j] = _compute_table[1][j - 1];
					}
				}
				else {
					if(COMP::equal(*xi,*yj)) {
						_compute_table[0][j] = _compute_table[1][j - 1] + 1;
					}
					else if(_compute_table[1][j] >= _compute_table[0][j - 1]) {
						_compute_table[0][j] = _compute_table[1][j];
					}
					else {
						_compute_table[0][j] = _compute_table[0][j - 1];
					}
				}
				++yj;
			}
			++xi;
		}
		_length = _compute_table[x_size%2][y_size];
		return _length;
	}
	inline IndexType Length() {
		return _length;
	}

private:
	Table _compute_table;//, _answer_table;
	IndexType _length;
	size_t _reserved;
};

#endif /* LCS_HPP_ */

/*
 * =====================================================================================
 *
 *       Filename:  lcs.hpp
 *
 *    Description:  A class of longest common subsequence (lcs) by dynamic programming
 *
 *        Version:  1.2
 *        Created:  2011年01月03日 20時15分32秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Dirk Chang (), [email protected]
 *        Company:  lc.asiahope.net
 *
 * =====================================================================================
 */
#ifndef LCS_HPP_
#define LCS_HPP_

#include <vector>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <iterator>
#include <algorithm>

struct Default_LCS_Comparison {
	template <typename T>
	static bool equal(T const &x, T const &y) {
		return x == y; // use operator == as the default comparison funtion
	}
};

template <typename COMP = Default_LCS_Comparison>
class LCS {
private:
	enum Direction { NIL = 0, LEFT, UPLEFT, UP };
	typedef size_t IndexType;
	typedef IndexType* Row;
	typedef std::vector<Row> Table;
	typedef std::vector<Direction*> AnsTable;

public:
	LCS(size_t const & reserved = 32) : _length(0), _m(0), _n(0), _reserved(reserved+1) {
		construct_table();
	}
	~LCS() {
		destory_table();
	}
	LCS(LCS const &l) : _length(l._length), _reserved(l._reserved) {
		construct_table();
		for(size_t i = 0; i < _reserved; ++i) {
			std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
			std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
		}
	}
	LCS const &operator=(LCS const &l) {
		_length = l._length;
		_reserved = l._reserved;
		destory_table();
		construct_table();
		for(size_t i = 0; i < _reserved; ++i) {
			std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
			std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
		}
	}

	template<typename const_iterator>
	inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
		_length = 0;
		_m = x_size;
		_n = y_size;

		size_t tmp_max = y_size;
		if(tmp_max < x_size) tmp_max = x_size;
		if(tmp_max >= _reserved) {
			_reserved = tmp_max + 1;
			destory_table();
			construct_table();
		}

		const_iterator xi, yj;
		xi = x_begin;
		size_t i(1), j(1);
		for(i = 1; i <= x_size; ++i) {
			yj = y_begin;
			for(j = 1; j <= y_size; ++j) {
				if(COMP::equal(*xi,*yj)) {
					_compute_table[i][j] = _compute_table[i - 1][j - 1] + 1;
					_answer_table[i][j] = UPLEFT;
				}
				else if(_compute_table[i - 1][j] >= _compute_table[i][j - 1]) {
					_compute_table[i][j] = _compute_table[i - 1][j];
					_answer_table[i][j] = UP;
				}
				else {
					_compute_table[i][j] = _compute_table[i][j - 1];
					_answer_table[i][j] = LEFT;
				}
				++yj;
			}
			++xi;
		}
		_length = _compute_table[x_size][y_size];
		return _length;
	}

	inline IndexType Length() {
		return _length;
	}

	template<typename SEQ, typename ANS>
	int Answer(const SEQ &x, ANS &answer) {
		construct_answer(x, _m, _n, answer);
		return 0;
	}

	void PrintComputeTable(std::ostream &out, int const tab = 2);
	void PrintAnswerTable(std::ostream &out, int const tab = 2);

private:
	template<typename SEQ, typename ANS>
	void construct_answer(const SEQ &x, int const i, int const j, ANS &answer) {
		if(i == 0 || j == 0) return;
		if(_answer_table[i][j] == UPLEFT) {
			construct_answer(x, i - 1, j - 1, answer);
			answer.push_back(x[i - 1]);
		}
		else if(_answer_table[i][j] == UP) {
			construct_answer(x, i - 1, j, answer);
		}
		else construct_answer(x, i, j - 1, answer);
	}

	void construct_table() {
		_compute_table.resize(_reserved, 0);
		_answer_table.resize(_reserved, 0);
		for(size_t i = 0; i < _reserved; ++i) {
			_compute_table[i] = new IndexType [_reserved];
			_answer_table[i] = new Direction [_reserved];
			_compute_table[i][0] = 0;
			_answer_table[i][0] = NIL;
		}
		for(size_t i = 0; i < _reserved; ++i) {
			_compute_table[0][i] = 0;
			_answer_table[0][i] = NIL;
		}
	}
	void destory_table() {
		for(size_t i = 0; i < _reserved; ++i) {
			delete [] _compute_table[i];
			delete [] _answer_table[i];
		}
	}

private:
	Table _compute_table;
	AnsTable _answer_table;
	IndexType _length, _m, _n;
	size_t _reserved;
};

template <typename COMP>
void LCS<COMP>::PrintAnswerTable(std::ostream &out, int const tab) {
	int i, j;
	out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
	for(i = 0; i < _n; ++i) {
		out << std::setw(tab) << i;
	}
	out << '\n';

	out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
	out << std::setw(tab) << '0' << std::setw(tab) << 'x';
	for(i = 0; i< _n; ++i) {
		out << std::setw(tab) << '0';
	}
	out << '\n';

	for(i = 1; i < _m; ++i) {
		out << std::setw(tab) << i << std::setw(tab) << ' ';
		for(j = 0; j < _n; ++j) {
			out << std::setw(tab) << _answer_table[i][j];
		}
		out << '\n';
	}
	out << '\n';
}


template <typename COMP>
void LCS<COMP>::PrintComputeTable(std::ostream &out, int const tab) {
	int i, j;
	out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
	for(i = 0; i < _n; ++i) {
		out << std::setw(tab) << i;
	}
	out << '\n';

	out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
	out << std::setw(tab) << '0' << std::setw(tab) << 'x';
	for(i = 0; i< _n; ++i) {
		out << std::setw(tab) << '0';
	}
	out << '\n';

	for(i = 1; i < _m; ++i) {
		out << std::setw(tab) << i << std::setw(tab) << ' ';
		for(j = 0; j < _n; ++j) {
			out << std::setw(tab) << _compute_table[i][j];
		}
		out << '\n';
	}
	out << '\n';
}

template <typename COMP = Default_LCS_Comparison>
class LCS_NOANS {
private:
	typedef size_t IndexType;
	typedef IndexType* Row;
	typedef std::vector<Row> Table;

public:
	LCS_NOANS(size_t const & reserved = 32) : _length(-1), _reserved(reserved+1) {
		_compute_table.resize(2, 0);
		_compute_table[0] = new IndexType [_reserved];
		_compute_table[1] = new IndexType [_reserved];
	}
	~LCS_NOANS() {
		delete [] _compute_table[0];
		delete [] _compute_table[1];
	}
	LCS_NOANS(LCS_NOANS const &l) : _length(l._length), _reserved(l._reserved) {
		_compute_table[0] = new IndexType [_reserved];
		_compute_table[1] = new IndexType [_reserved];
		std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
		std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
	}
	LCS_NOANS const &operator=(LCS_NOANS const &l) {
		_length = l._length;
		_reserved = l._reserved;
		delete [] _compute_table[0];
		delete [] _compute_table[1];
		_compute_table[0] = new IndexType [_reserved];
		_compute_table[1] = new IndexType [_reserved];
		std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
		std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
	}

	template<typename const_iterator>
	inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
		_length = 0;

		size_t tmp_max = y_size;
		if(tmp_max < x_size) tmp_max = x_size;
		if(tmp_max >= _reserved) {
			_reserved = tmp_max + 1;
			delete [] _compute_table[0];
			delete [] _compute_table[1];
			_compute_table[0] = new IndexType [_reserved];
			_compute_table[1] = new IndexType [_reserved];
		}
		std::memset(_compute_table[0], 0, sizeof(IndexType)*_reserved);
		std::memset(_compute_table[1], 0, sizeof(IndexType)*_reserved);

		const_iterator xi, yj;
		xi = x_begin;
		size_t i(1), j(1);
		for(i = 1; i <= x_size; ++i) {
			yj = y_begin;
			_compute_table[i%2][0] = 0;
			for(j = 1; j <= y_size; ++j) {
				if(i%2) {
					if(COMP::equal(*xi,*yj)) {
						//std::cout << "(" << *xi << "," << *yj << ")";
						_compute_table[1][j] = _compute_table[0][j - 1] + 1;
					}
					else if(_compute_table[0][j] >= _compute_table[1][j - 1]) {
						_compute_table[1][j] = _compute_table[0][j];
					}
					else {
						_compute_table[1][j] = _compute_table[1][j - 1];
					}
				}
				else {
					if(COMP::equal(*xi,*yj)) {
						_compute_table[0][j] = _compute_table[1][j - 1] + 1;
					}
					else if(_compute_table[1][j] >= _compute_table[0][j - 1]) {
						_compute_table[0][j] = _compute_table[1][j];
					}
					else {
						_compute_table[0][j] = _compute_table[0][j - 1];
					}
				}
				++yj;
			}
			++xi;
		}
		_length = _compute_table[x_size%2][y_size];
		return _length;
	}
	inline IndexType Length() {
		return _length;
	}

private:
	Table _compute_table;//, _answer_table;
	IndexType _length;
	size_t _reserved;
};

#endif /* LCS_HPP_ */

LCS header file

C++