lcs.cpp

求最长公共子序列的算法

#include <iostream>
#include <string>
using namespace std;

enum DIRECTION{LEFT,TOP,LEFT_TOP,NONE};

//动态二维数组
template <class T>
class Matrix {
public:
	Matrix(int row, int col)
	{
		if (row<=0 || col<=0)
			exit(0);
		ROW = row;
		COL = col;
		matrix = new T[row*col];
	}
    ~Matrix()
    {
		delete[] matrix;
    }
	T GetValue(int m, int n)
	{
		if (m<0 || m>=ROW || n<0 || n>=COL)
			exit(0);
		return matrix[m*COL+n];
	}
	void SetValue(int m, int n, T value)
	{
		if (m<0 || m>=ROW || n<0 || n>=COL)
			exit(0);
		matrix[m*COL+n] = value;
	}
public:
	T *matrix;
	int ROW;
	int COL;
};

class LCS {
public:
    LCS(string string1, string string2);
   ~LCS();
    string GetLCS();
private:
	LCS();
	Matrix<int> *VALUEtable;
	Matrix<DIRECTION> *DIREtable;
	string str1;
	string str2;
};

LCS::LCS(string string1, string string2)
{
	str1 = string1;
	str2 = string2;
	VALUEtable = new Matrix<int>(str1.length()+1,str2.length()+1);
	DIREtable = new Matrix<DIRECTION>(str1.length()+1,str2.length()+1);
}

LCS::~LCS()
{
	delete VALUEtable;
	delete DIREtable;
}

string LCS::GetLCS()
{
	int i,j;
	for (i=0; i<VALUEtable->ROW; i++)
	{
		VALUEtable->SetValue(i, 0, 0);
		DIREtable->SetValue(i, 0, NONE);
	}
	for (j=0; j<VALUEtable->COL; j++)
	{
		VALUEtable->SetValue(0 ,j ,0);
		DIREtable->SetValue(0, j, NONE);
	}

	for (i=1; i<VALUEtable->ROW; i++)
		for (j=1; j<VALUEtable->COL; j++)
		{
			if(str1[i-1] == str2[j-1])
			{
				VALUEtable->SetValue(i, j, (VALUEtable->GetValue(i-1,j-1))+1);
				DIREtable->SetValue(i, j, LEFT_TOP);
			}
			else if (VALUEtable->GetValue(i-1, j) >= VALUEtable->GetValue(i, j-1))
			{
				VALUEtable->SetValue(i, j, VALUEtable->GetValue(i-1, j));
				DIREtable->SetValue(i, j, TOP);
			}
			else
			{
				VALUEtable->SetValue(i, j, VALUEtable->GetValue(i, j-1));
				DIREtable->SetValue(i, j, LEFT);
			}
		}
	
	string opLCSstr = "";
	int rowIndex = VALUEtable->ROW - 1;
	int colIndex = VALUEtable->COL - 1;
	i = 0;

	DIRECTION dir = DIREtable->GetValue(rowIndex, colIndex);
	while (dir != NONE)
	{		
		if (dir == LEFT_TOP)
		{
			opLCSstr.insert(opLCSstr.end(),str2[colIndex-1]);
			rowIndex--;
			colIndex--;
			i++;
		}
		else if (dir == LEFT)
			colIndex--;
		else
			rowIndex--;

		dir = DIREtable->GetValue(rowIndex, colIndex);
	}


	int tempLength = opLCSstr.length();
	string LCSstr = "";	
	for (int k=1; k<=tempLength; k++)
		LCSstr.insert(LCSstr.end(),opLCSstr[tempLength-k]);
	return LCSstr;
} 

int main ()
{
	string str1 = "ABCBDAB";
	string str2 = "BDCABA";
	LCS sample1(str1, str2);
	cout << "The LCS of the " << endl 
		 << "string " << str1 << endl 
		 << "and" << endl 
		 << "string " << str2 << endl
	     << "is:" << endl
		 << sample1.GetLCS() << "\n\n\n";

    system("pause"); 
	return 0;
}