现在的位置: 首页 > 综合 > 正文

动态规划-最长公共子序列

2013年12月06日 ⁄ 综合 ⁄ 共 1161字 ⁄ 字号 评论关闭

assuming i,j start from 1;
               0,                                  ( i=0 or j=0)
  c(i,j)=   c(i-1,j-1)+1                      ( i,j>0 and A[i]=B[j])
              Max( c[i-1,j),c(i,j-1))       ( i,j>0 and A[i]!=B[j])

 

时间复杂度O(m*n),空间复杂度O(m*n)

#define MAX 100
int C[MAX][MAX];
int D[MAX][MAX];
//输出子序列
void Print_LCSub(char *str,int i,int j){
	if(i==0|| j==0)
		return;
	if(D[i][j]==0){
		Print_LCSub(str,i-1,j-1);
		cout<<str[i-1];
	}
	else if(D[i][j]==1)
		Print_LCSub(str,i-1,j);
	else
		Print_LCSub(str,i,j-1);
}
void LCSubsequence(char *str1,char *str2){
	int len1,len2;
	int i,j;
	len1=strlen(str1);
	len2=strlen(str2);
	for(i=0;i<=len1;i++)
		C[i][0]=0;
	for(j=1;j<=len2;j++)
		C[0][j]=0;
	for(i=1;i<=len1;i++){
		for(j=1;j<=len2;j++){
			if(str1[i-1]==str2[j-1]){
				C[i][j]=C[i-1][j-1]+1;
				D[i][j]=0; // left and up
			}
			else if(C[i-1][j]>=C[i][j-1]){
				C[i][j]=C[i-1][j];
				D[i][j]=1; // up 
			}
			else
			{
				C[i][j]=C[i][j-1];
				D[i][j]=-1; // left 

			}
		}
	}
	//output matrix
	for(i=0;i<=len1;i++){
		for(j=0;j<=len2;j++)
			cout<<setw(2)<<C[i][j]<<" ";
		cout<<endl;
	}
	cout<<"MaxLen="<<C[len1][len2]<<endl;
	Print_LCSub(str1,len1,len2);
	cout<<endl;
}

void main(){
	char str1[200]="xab4c3de89fgh";
	char str2[200]="ac234egxxh9";
	//freopen("D:/test.txt","r",stdin);

	LCSubsequence(str1,str2);
	
}

 输出结果:
                        

抱歉!评论已关闭.