最长公共子序列.cpp

算法设计分析的一些例子程序....凑字数..凑字数

#include <iostream> 
using namespace std;
void L(int m,int n,char *x,char *y,int c[8][7],char b[8][7])
{ 
	int i,j;
	for(i=1;i<=m;i++)
		c[i][0]=0;
	for(i=1;i<=n;i++)
		c[0][i]=0;
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
	{
		if(x[i-1]==y[j-1])
		{
			c[i][j]=c[i-1][j-1]+1;
		    b[i][j]='a';
		}
		else if(c[i-1][j]>=c[i][j-1])
		{
			c[i][j]=c[i-1][j];
			b[i][j]='b';
		}
		else 
		{
			c[i][j]=c[i][j-1];
			b[i][j]='c';
		}
	}
	cout<<"最长公共子序列长度为  "<<c[7][6]<<"    子序列为"<<endl;
}


void out(int i,int j,char  * x,char b[8][7])
{
	if(i==0||j==0)  return;
	if(b[i][j]=='a')
	{
		out(i-1,j-1,x,b);
		cout<<x[i-1]<<"   ";
	}
	else if(b[i][j]=='b')
		out(i-1,j,x,b);
	else if(b[i][j]=='c')
		out(i,j-1,x,b);
}


int main()
{ 
	char x[]="ABCBDAB";
	char y[]="BDCABA";
	int c[8][7]={0};
	char b[8][7]={0};
	L(7,6,x,y,c,b);
	out(7,6,x,b);
	return 0; 
}