lcs2.cpp

用分治法求出两个字符串中的最长公共子序列

#include<iostream.h>
#include<string.h>


int lcsLength(char x[],char y[],int b[8][7]);
void lcs(int i,int j,char x[],int b[8][7]);

void main()
{
	char x[]={'A','B','C','B','D','A','B',0};
	char y[]={'B','D','C','A','B','A',0};
	int b[8][7];
	int sum;
	cout<<"x,y最长公共子序列长度为：\n";
    sum=lcsLength(x,y,b);
	cout<<sum<<endl;
	cout<<"x,y最长公共子序列为：\n";
	lcs(8,7,x,b);
	cout<<endl;
    
}
int lcsLength(char x[],char y[],int b[8][7])
{
	int c[8][7];
	int m=strlen(x);
	int n=strlen(y);
	//int m=7;
	//int n=6;
  
	for(int l=1;l<=m;l++)
	{
		c[l][0]=0;
	}
	for(int r=1;r<=n;r++) 
	{
		c[0][r]=0;
	}
    for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(x[i-1]==y[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}

		}
	}
	return c[m][n];

}
void lcs(int i,int j,char x[],int b[8][7])
{
	if(i==0||j==0) return;
	if(b[i][j]==1)
	{
		lcs(i-1,j-1,x,b);
		cout<<x[i-1];
	}
	else if(b[i][j]==2)
	{
		lcs(i-1,j,x,b);
	}
	else
	{
		lcs(i,j-1,x,b);
	}
}