周恒-6分.txt

这是很不错的计算机算法

#include <stdlib.h>
#include <fstream.h>
#include <iostream.h>

char *x,*y,**b;
int **c;
ofstream fout("output.txt");

void LCSLength(int m,int n,char *x,char *y,int **c,char **b)
{
	int i,j;
	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]==y[j])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]='X';
			}
			else if (c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]='^';
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]='<';
			}
		}
}

void LCS(int i,int j,char *x,char **b)
{
	if (i==0||j==0) return;
	if (b[i][j]=='X')
	{
		LCS(i-1,j-1,x,b);
		fout << x[i];
	}
	else if (b[i][j]=='^') LCS(i-1,j,x,b);
	else LCS (i,j-1,x,b);
}

void main()
{
	int m,n,i;

	ifstream fin("input.txt");
	if(fin.fail())
	{
		cout << "no input.txt!";
		exit(1);
	}
	fin >> n >> m;

	if((x=new char [n+1])==NULL)
	{
		cout << "No memory!" << endl;
		exit (1);
	}
	for (i=1;i<=n;i++) fin >> x[i];

	if((y=new char [m+1])==NULL)
	{
		cout << "No memory!" << endl;
		exit (1);
	}
	for (i=1;i<=m;i++) fin >> y[i];
	fin.close();

	//分配内存给c[n+1][m+1]
	if((c=new int*[n+1])==NULL)
	{
		cout << "No memory!" << endl;
		exit (1);
	}
	for (i=0;i<=n;i++ )
	{
		if((c[i]=new int[m+1])==NULL)
		{
			cout << "No memory!" << endl;
			exit (1);
		}
	}

	//分配内存给b[n+1][m+1]
	if((b=new char*[n+1])==NULL)
	{
		cout << "No memory!" << endl;
		exit (1);
	}
	for (i=0;i<=n;i++)
	{
		if((b[i]=new char[m+1])==NULL)
		{
			cout << "No memory!" << endl;
			exit (1);
		}
	}

	LCSLength(n,m,x,y,c,b);
	fout << c[n][m] << endl;
	LCS(n,m,x,b);

	fout.close();

	//释放内存
	for(i=0;i<=n;i++) delete[] b[i];
	delete[] b;
	for(i=0;i<=n;i++) delete[] c[i];
	delete[] c;
	delete[] y;
	delete[] x;
	
	return;
}