lcs.cpp

动态规划实现lcs

#include <iostream>
#include <string>

using namespace std;


static int length = 0; //保存最长公共子序列的长度
static int maxLength = 0;//记录最长子序列长度
static int count = 0;


int max(int a,int b)
{
	return a>=b?a:b;


}
void lcsLength(string& str_x,string &str_y,int **b)
{
	int xMaxIndex=(int)str_x.length()-1;
	int yMaxIndex=(int)str_y.length()-1;
	
	int **count;                                      
	
	count = new int*[str_x.length()+1];
	
	for (int i = 0; i < (int) str_x.length() ; i++)
	{
		count[i] = new int[str_y.length()+1];
	}
	

	for(i=0;i <=xMaxIndex;i++)
	{
		count[i][1]=0;
	}
	
	for(i=0;i <=yMaxIndex;i++)
	{
		count[0][i]=0;
	}

	for(i=1;i <=xMaxIndex;i++)
		for(int j=1;j <=yMaxIndex;j++)
		{
			if(str_x[i]==str_y[j]) //如果相等 则对角线加一
			{
				count[i][j]=count[i-1][j-1]+1;
				maxLength = max(maxLength,count[i][j]);
				b[i][j]=1;
			}
			                        //如果不等,则比较上方和左方,取最大值
			else 
				if(count[i-1][j]>count[i][j-1])    //上方大
			{
				count[i][j]=count[i-1][j];
				maxLength = max(maxLength,count[i][j]);
				b[i][j]=2;
			}
			else
				if (count[i-1][j]<count[i][j-1])     //左方大
			{
				count[i][j]=count[i][j-1];
				maxLength = max(maxLength,count[i][j]);
				b[i][j]=3;
			}
			else 
			{
				count[i][j]=count[i-1][j];
				maxLength = max(maxLength,count[i][j]);
				b[i][j]=4;
			}
		}
}


void lcs(int i,int j,string & x,int **b,string strResult)
{
	if(i==0 || j==0)
	{
		return;
	}
	if(b[i][j]==1)
	{
		strResult = x[i] + strResult;
		if (strResult.length() == maxLength) 
		{
			cout<<"Length = " << strResult.length() <<"\nLCS = " <<strResult<<endl;		
		}		
		lcs(i-1,j-1,x,b,strResult);
	}
	else
		if(b[i][j]==2)
	{
		lcs(i-1,j,x,b,strResult);
	}
	else 
		if(b[i][j]==3)
	{
		lcs(i,j-1,x,b,strResult);
	}
	else 
		if(b[i][j]==4)                     
	{
		lcs(i-1,j,x,b,strResult);
		lcs(i,j-1,x,b,strResult);
	}     
}





int main()
{
	string  str_same = "";  //保存最长公共子序列	

	
	string str_x="";
	string str_y="";
    

	cout<<"please enter two strings"<<endl; //输入两个字符串
	cin>>str_x;
	cin>>str_y;


	str_x=" " + str_x;        
	str_y=" " + str_y;

	int **b;
	b = new int*[str_x.length()];

	for (int i = 0; i <(int) str_x.length() ; i++)
	{
		b[i] = new int[str_y.length()];
	}
		
	lcsLength(str_x,str_y,b);
	
	lcs((int)str_x.length()-1,(int)str_y.length()-1,str_x,b,str_same);

	return 1;
}