LCS算法

求两个序列的最长公共子序列

x序列为：zxyxyz

y序列为：xyyzx

(动态规划--C语言实现)

#include <stdio.h>

void print(int i,int j,char x[],int a[][6]){
    if(i==0||j==0)
        return;
    if(a[i][j]==1){
        print(i-1,j-1,x,a);
        printf("%c",x[i]);
    }else if(a[i][j]==2){
        print(i,j-1,x,a);
    }else{
        print(i-1,j,x,a);
    }
}

int main()
{
	int i,j;
    char x[]={'0','z','x','y','x','y','z'};
    char y[]={'0','x','y','y','z','x'};
    int a[7][6]={0};
    int lcs[7][6]={0};
	for(i=1;i<=6;i++){
		for(j=1;j<=5;j++){
			if(x[i]==y[j]){
			    lcs[i][j]=lcs[i-1][j-1]+1;
			    a[i][j]=1;
			}else
			    if(lcs[i][j-1]>=lcs[i-1][j]){
			        lcs[i][j]=lcs[i][j-1];
			        a[i][j]=2;
			    }else{
			        lcs[i][j]=lcs[i-1][j];
			        a[i][j]=3;
			    }
		}
	}
	for(i=0;i<=6;i++){
	    for(j=0;j<=5;j++){
	        printf("lcs[%d][%d]=%d\t",i,j,lcs[i][j]);
	    }
	    printf("\n");
	}
	printf("最大子序列长度为：%d\n",lcs[6][5]);
	printf("最长子序列为：");
	print(6,5,x,a);
    return 0;
}