吴小菁-6分.txt

这是很不错的计算机算法

#include <stdio.h>
#include <fstream.h>
#include <iostream.h>
#include<stdlib.h>
//using namespace std;
ofstream out("output.txt");
ifstream in("input.txt",ios::nocreate); 
//int **c,**b;
void LCSLength(int m,int n,char * x,char * y,int **c,int **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]=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;
		  }
	  }
	   out<<c[m][n]<<endl;
}
void LCS(int i,int j,char *x,int **b)
{
	if(i==0||j==0) return;
	if (b[i][j]==1)
	{
		LCS(i-1,j-1,x,b);
		out<<x[i];
	}
	else if (b[i][j]==2) LCS(i-1,j,x,b);
	else LCS(i,j-1,x,b);
}

int main()
{
	int i,j,m,n;
	char *x,*y;
    if (!in)
	{
        cerr<<"the input.txt is not exist!";
        exit(-1);
	}
	in>>m>>n;
	x=new char[m];
	y=new char[n];
	int **c=new int *[m];
	for (i=0;i<=m;i++)
		c[i]=new int[n];
    int **b=new int *[m];
	for (i=0;i<=m;i++)
		b[i]=new int[n];
    for(i=1;i<=m;i++) 
	{in>>x[i];}
	for(j=1;j<=n;j++) 
	{in>>y[j];}
	LCSLength(m,n,x,y,c,b);
	LCS(m,n,x,b);
	in.close();
	out.close();
     return 0;
}