subsequence.cpp

最长子序列的求解,用于查找几个序列中最长的公共子序列

#include <iostream>
using namespace std;
int lcs(char A[],char B[],char C[],int n,int m)
{   
	int i,j,k,len;
	int (*L)[11]=new int [11][11];
	int (*s)[11]=new int [11][11];
	for(i=0;i<=n;i++)
		L[0][i]=0;
	for(j=0;j<=m;j++)
		L[j][0]=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(A[i]==B[j]){
				L[i][j]=L[i-1][j-1];
				s[i][j]=1;
			}
			else if(L[i-1][j]>=L[i][j-1]){
				L[i][j]=L[i-1][j];
				s[i][j]=2;
			}
			else { 
				L[i][j]=L[i][j-1];
				s[i][j]=3;
			}
	i=n;j=m;k=len=L[n][m];
	while((i!=0)&&(j!=0)){
		switch(s[i][j]){ 
		case 1:  C[k]=A[i];k--;j--;
		case 2:  i--;break;
		case 3:  j--;break;
		}
	//	delete L;delete s;
		return len;
	}
 int main()
 {   //int lcs(char A[],char B[],int n,int m);
	char a[10];
	char b[10];
	char c[10];
	cout<<"input a"<<endl;
    for(int k=0;k<=9;k++)
	{
	  cin>>a[k];
	}
	cout<<"input b"<<endl;
	for(int h=0;h<=9;h++)
	{ 
        cin>>b[h];
	}
    int length=lcs(a,b,c,10,10);
	for(;length>=0;length--)
	{ 
		cout<<c[length-1];
	}
	return 0;
 }