lcsub.cpp

求最长公共字串的代码

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

//动态二维数组
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)//相当于Matrix[m][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)//相当于Matrix[m][n]，注意越界
	{
		if (m<0 || m>=ROW || n<0 || n>=COL)
			exit(0);
		matrix[m*COL+n] = value;
	}
public:
	T *matrix;
	int ROW;
	int COL;
};

class LCSub {
public:
    LCSub(string string1, string string2);
   ~LCSub();
    string GetLCSub();//得到最长公共子串
private:
	LCSub();
	string str1;
	string str2;
	Matrix<int> *VALUEtable;
};

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

LCSub::~LCSub ()
{
	delete VALUEtable;
}

string LCSub::GetLCSub ()
{
    int i,j;

	//初始化表格
	for (i=0; i<VALUEtable->ROW; i++)
		VALUEtable->SetValue(i, 0, 0);

	for (j=0; j<VALUEtable->COL; j++)
		VALUEtable->SetValue(0 ,j ,0);

	//记录最大值
	int MAXROWINDEX;
	int MAXCOLINDEX;
	int MAXVALUE = -1;
	int CURR;

	//填表
    for (i=1; i<VALUEtable->ROW; i++)
		for (j=1; j<VALUEtable->COL; j++)
		{
			if(str1[i-1] == str2[j-1])
			{
				CURR = VALUEtable->GetValue(i-1,j-1)+1;
				VALUEtable->SetValue(i, j, CURR);
				if (CURR > MAXVALUE)
				{
					MAXVALUE = CURR;
					MAXROWINDEX = i;
					MAXCOLINDEX = j;
				}
			}
			else
				VALUEtable->SetValue(i, j, 0);
		}

	 //构造最优解
     string opLCSubstr = "";
	 i = 0;
	 while (MAXVALUE != 0)
	 {
		 opLCSubstr.insert(opLCSubstr.end(),str2[MAXCOLINDEX-1]);
		 MAXCOLINDEX--;
         MAXVALUE--;
	 }

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

int main ()
{
	string str1 = "xzyzzyx";
	string str2 = "zxyyzxz";
	LCSub sample1(str1, str2);
	cout << "The LCSub of the " << endl 
		 << "string " << str1 << endl 
		 << "and" << endl 
		 << "string " << str2 << endl
	     << "is:" << endl
		 << sample1.GetLCSub() << "\n\n\n";

	string str3 = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCALLAAQANKESSSESFISRLLAIVAD";
	string str4 = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCTLLAAQANKENSNESFISRLLAIVAG";
	LCSub sample2(str3, str4);
	cout << "The LCSub of the " << endl 
		 << "string " << str3 << endl 
		 << "and" << endl 
		 << "string " << str4 << endl
	     << "is:" << endl
		 << sample2.GetLCSub() << "\n\n\n";
	return 0;
}