最长公共子序列.cpp

前一阵出去玩了

#include <iostream.h>
void LCSLength(int m,int n,char *x,char *y,int **c,int **b)
{
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]==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;
         }
	  }
cout<<c[m][n]<<endl;
if (c[m][n]==0)
cout<<"there is no match!"<<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);
        cout<<x[i];
     }
   else if (b[i][j]==2)LCS(i-1,j,x,b);
   else LCS(i,j-1,x,b);
}
void main()
{
	int i,m,n;
	cout<<"please input first order's length!"<<endl;
	cin>>m;
	cout<<"please input second order's length!"<<endl;
	cin>>n;
	char *x=new char [m];
	char *y=new char [n];
	cout<<"please input your firsr order!"<<endl;
	for (i=1;i<=m;i++)
		cin>>x[i];
	cout<<"please input your second order!"<<endl;
	for (i=1;i<=n;i++)
		cin>>y[i];
	int **c=new int *[m+1];
	for (i=0;i<=m;i++)
		c[i]=new int [n+1];
    int **b=new int *[m+1];
	for (i=0;i<=m;i++)
		b[i]=new int [n+1];
    LCSLength(m,n,x,y,c,b);
	LCS(m,n,x,b);
	cout<<endl;
}