最长公共子序列

给定两个序列X=<x1,x2,x3,x4…xm>和Y=<y1,y2,y3,y4…yn>,求X和Y长度最长的公共子序列。

可以用动态规划的方法解决这个问题,建立数组c[i][j]，i和j分别表示X_i 和Y_j的的LCS长度，如果i=0,j=0,c[i][j]=0,根据最优子结构的性质，得到问题的递推公式为：

建立数组b[i][j]，如果b[i][j]=0,代表c[i][j]=c[i-1][j-1]+1的情况，如果b[i][j]=-1,代表c[i][j]=c[i][j-1]的情况，如果b[i][j]=1,代表c[i][j]=c[i-1][j]的情况。数组b[i][j]在递归地构造LCS时会用到。

程序为：

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# define N 100
int main()
{
	int f1(char *a,char *b,int c[][N],int d[][N]);
	void print(int b[][N],char *a,int i,int j);
	char a[20]="abcrty";
	char b[20]="aerbtyc";
	int c[N][N];
	int d[N][N];
	int i,j;
	char *s=0; 
	f1(a,b,c,d);
	print(d,a,strlen(a),strlen(b));
system("pause");
return 0;
}
int f1(char *a,char *b,int c[][N],int d[][N])
{
int lena=strlen(a);
int lenb=strlen(b);
int i=0;
int j=0;
for(i=0;i<=lena;i++)              //c[i][j]的初始化
	c[i][0]=0;
for(j=0;j<=lenb;j++)
	c[0][j]=0;
for(i=1;i<=lena;i++)              //递推公式
	for(j=1;j<=lenb;j++)
	{
	if(a[i-1]==b[j-1]){
		c[i][j]=c[i-1][j-1]+1;
		d[i][j]=0;
	}
	else if(c[i-1][j]>c[i][j-1]){
		c[i][j]=c[i-1][j];
		d[i][j]=1;
	}
	else
	{
		c[i][j]=c[i][j-1];
		d[i][j]=-1;
	}
	}
	return 0;
}

void print(int b[][N],char *a,int i,int j)   //递归的方法构造LCS
{
	if(i==0||j==0)
		return ;

	if(b[i][j]==0){
		print(b,a,i-1,j-1);
		printf("%c\t",a[i-1]);
	}
	else if (b[i][j]==1)
		print(b,a,i-1,j);
	else
		print(b,a,i,j-1);
}

上面的代码使用了附加空间b数组，在构造LCS时采用了递归，因为程序的效率较低，对上面的代码稍作优化，不使用数组b,构造用循环的方式构造LCS。代码如下：

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# define N 100
int main()       
{
	int f(char *a,char *b,int c[][N]);
	char * lcs(char s[],char *a,char *b,int c[][N]);
	char a[20]="abcrty";
	char b[20]="aerbtyc";
	int c[N][N];
	int d[N][N];
	int i,j;
	char *s=0; 
	f(a,b,c);
	s=lcs(s,a,b,c);
	printf("%s\n",s);
system("pause");
return 0;
}

int f(char *a,char *b,int c[][N])
{
int lena=strlen(a);
int lenb=strlen(b);
int i=0,j=0;
for(i=0;i<=lena;i++)    //初始化
	c[i][0]=0;
for(j=0;j<=lenb;j++)
	c[0][j]=0;
for(i=1;i<=lena;i++)       //递推公式
	for(j=1;j<=lenb;j++)
	{
	if(a[i-1]==b[j-1])
		c[i][j]=c[i-1][j-1]+1;
	else if(c[i-1][j]>c[i][j-1])
		c[i][j]=c[i-1][j];
	else
		c[i][j]=c[i][j-1];
	}
	return c[lena][lenb];
}

char * lcs(char s[],char *a,char *b,int c[][N])
{
int i=strlen(a);
int j=strlen(b);
int k=f(a,b,c);
s=(char *)malloc(k*sizeof(char));
s[k]=‘\0‘;
while(k>0)
{
	if(c[i][j]==c[i-1][j])
		i--;
	else if(c[i][j]==c[i][j-1])
		j--;
	else 
	{
	
	s[--k]=a[i-1];
	i--;j--;
	}
}
return s;       //最长公共子序列
}

最长公共子序列,布布扣,bubuko.com

最长公共子序列

原文：http://blog.csdn.net/u011608357/article/details/24527057