lcs.cpp

最大公共子序列 采用动态规划发

#include <iostream>
#include <vector>
#define MAX 150
using std::cout;
using std::cin;
using std::vector;
using std::endl;
//A,B为两个序列，m,n分别为两个序列的长度，c存放最优解值，b为解矩阵
void LCS_length(vector<int> A,vector<int> B,int m,int n,int c[MAX][MAX],int b[MAX][MAX])
{
	int i,j;
	for(i=0;i<=m;i++)
		c[i][0]=0;
	for(j=0;j<=n;j++)
		c[0][j]=0;
	//b[i][j]=10时c[i, j]由c[i, j-1]确定
	//b[i][j]=20时c[i, j]由c[i-1, j-1]确定
	//b[i][j]=30时c[i, j]由c[i-1, j]确定
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			if(A[i-1]==B[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=20;
			}
            else
			{
				if(c[i-1][j]>=c[i][j-1])
				{
					c[i][j]=c[i-1][j];
                    b[i][j]=30;
				}
				else
				{
					c[i][j]=c[i][j-1];
					b[i][j]=10;
				}
			}
		}
}
void print_LCS(int bb[MAX][MAX],vector<int> x,int a,int b)
{
	if(a==0||b==0)
		return;
	if(bb[a][b]==20)
	{
		print_LCS(bb,x,a-1,b-1);
		cout<<" "<<x[a-1];
	}
	else if(bb[a][b]==30)
		print_LCS(bb,x,a-1,b);
	else
		print_LCS(bb,x,a,b-1);
}
void main ()
{
	int xLength=0,yLength=0;
	vector<int> X;
	vector<int> Y;
	int data;
	cout<<"请输入X序列，输入元素为正整数！输入99999时表示输入结束！"<<endl;
    cin>>data;
	while(data!=99999)
	{
		X.push_back(data);
		xLength++;
		cin>>data;
	}
    cout<<"请输入Y序列，输入元素为正整数！输入99999时表示输入结束！"<<endl;
    cin>>data;
	while(data!=99999)
	{
		Y.push_back(data);
		yLength++;
		cin>>data;
	}
	cout<<"X序列的元素个数为"<<xLength<<endl;
    cout<<"Y序列的元素个数为"<<yLength<<endl;
	int cmatrix[MAX][MAX];
	int bmatrix[MAX][MAX]={0};
	LCS_length(X,Y,xLength,yLength,cmatrix,bmatrix);
	cout<<"X,Y的最大公共子序列"<<endl;
	print_LCS(bmatrix,X,xLength,yLength);
}