公共子序列.cpp

一个简单的求公共子序列的源程序,自己编的,有点简单,提供给初学的学生参考.

#include <iostream.h>
char x[8]={' ','A','B','C','B','D','A','B'};
char y[7]={' ','B','D','C','A','B','A'};
int l[8][7];
char b[8][7];
void main ()
{
	int i;
	cout<<"X的内容为：";
	for(i=1;i<=7;i++)
		cout<<x[i];
	cout<<endl;
	cout<<"Y的内容为：";
	for(i=1;i<=6;i++)
		cout<<y[i];
	cout<<endl;
	void longlength();
	longlength();
	void output (int i,int j);
	cout<<endl<<"最长的公共子序列为：";
	output(7,6);
	cout<<endl;
}
void longlength ()
{
	int i,j;
	for(i=0;i<=7;i++)
		l[i][0]=0;
	for(j=1;j<=6;j++)
		l[0][j]=0;
	for(i=1;i<=7;i++)
	{
		for(j=1;j<=6;j++)
		{
			if(x[i]==y[j])
			{
				l[i][j]=l[i-1][j-1]+1;
				b[i][j]='t';
			}
			else if(l[i-1][j]>=l[i][j-1])
			{
				l[i][j]=l[i-1][j];
				b[i][j]='a';
			}
			else
			{
				l[i][j]=l[i][j-1];
				b[i][j]='l';
			}
		}
	}
	cout<<endl<<"L表的内容为："<<endl;
	for(i=0;i<=7;i++)
	{
		for(j=0;j<=6;j++)
			cout<<l[i][j]<<' ';
		cout<<endl;
	}
	cout<<endl<<"B表的内容为："<<endl;
	for(i=0;i<=7;i++)
	{
		for(j=0;j<=6;j++)
			cout<<b[i][j]<<' ';
		cout<<endl;
	}
}
void output (int i,int j)
{
	if(i==0) 
		return;
	if(j==0)
		return;
	if(b[i][j]=='t')
	{
		output(i-1,j-1);
		cout<<x[i];
	}
	else 
		if(b[i][j]=='a')
			output(i-1,j);
		else
			output(i,j-1);
}