Demo entry 6656656

最长公共子序列

   

Submitted by anonymous on Nov 01, 2017 at 06:56
Language: C++. Code size: 2.1 kB.

#include<iostream>
using namespace std;
//¼ÆËãLCSµÄ³¤¶È
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(j=0;j<=n;j++)
                  c[0][j]=0;
                                                  
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(x[i]==y[j])   //Çé¿ö1 
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;
			}
			else if(c[i-1][j]>=c[i][j-1]){   //Çé¿ö2 
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}
			else {                           //Çé¿ö3 
				c[i][j]=c[i][j-1];
			    b[i][j]=3;   
                } //b[i][j]¼Ç¼c[i][j]ÊÇÓÉÄÄÒ»¸ö×ÓÎÊÌâµÄ½âµÃµ½µÄ
		}
	}


}
//´òÓ¡³öÐòÁÐXºÍYµÄ×¹«¹²×ÓÐòÁÐ
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);
}
int main(){
    int t,m,n,i,j=1;
    char*x,*y;
    int**c,**b;
    cin>>t;
    while(t>0){
                 cin>>m>>n;
                 x=new char[m+1];
                 y=new char[n+1];
                 c=new int*[m+1];
                 b=new int*[m+1];
                 for(i=0;i<=m;i++){
                     c[i]=new int[n+1];
                     b[i]=new int[n+1];
                                   }
                 for(i=1;i<=m;i++)
                     cin>>x[i];
                 for(i=1;i<=n;i++)
                     cin>>y[i];
                 LCSLength(m,n,x,y,c,b);
                 cout<<"c table"<<endl;
                 for(i=1;i<=m;i++){
                   for(j=1;j<=n;j++)
                     cout<<c[i][j]<<"";
                     cout<<endl;
                                   }   
                 cout<<"b table"<<endl;
                 for(i=1;i<=m;i++){
                    for(j=1;j<=n;j++)
                    cout<<b[i][j]<<" ";
                    cout<<endl;
                 }
                 cout<<"case"<<j++<<endl;
                 cout<<c[m][n]<<"LCS(X,Y):";
                 LCS(m,n,x,b);
                 cout<<endl;
   }

}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).