子序列.cpp

经典的求最长子序列问题

#include<iostream.h>
#include<string.h>
lcs(char *x,char *y)
{
	int i,j,m,n,c[20][20];
	char x2[20];
	m=strlen(x);
	n=strlen(y);
	for (i=0;i<=m;++i)
		c[i][0]=0;
	for (i=0;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;
				x2[c[i][j]-1]=x[i-1];
			}
			else if (c[i-1][j]>=c[i][j-1])
				c[i][j]=c[i-1][j];
			else c[i][j]=c[i][j-1];
		}
	}
	cout<<"最长公共子序列长度为:"<<c[m][n]<<endl<<"最长公共子序列为:";
	for(i=0;i<c[m][n];i++)
		cout<<x2[i];
	cout<<endl;
	return 0;
}
main()
{
	int i;
	char x[20],y[20];
	cout<<"注意:序列最大长度不能超过20"<<endl;
	cout<<"请输入序列x(不含空格):"<<endl;
	cin>>x;
	cout<<"请输入序列y(不含空格):"<<endl;
	cin>>y;
	lcs(x,y);
	cout<<"--copyright(c)2004 youngerstudio--";
	cin>>y;
	return 0;
}