算法精解:最长公共子序列

  1. 云栖社区>
  2. 博客>
  3. 正文

算法精解:最长公共子序列

morixinguan 2016-06-29 10:31:00 浏览394
展开阅读全文

最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。
其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,
且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
而最长公共子串(要求连续)和最长公共子序列是不同的

设序列 X 存储在数组 x[m]中,序列 Y 存储在数组 y[n]中, 二维数组 L[m+1][n+1]
存储最长公共子序列的长度的迭代过程, S[ m + 1] [n + 1]存储相应的状态, 最长公共子
序列存储在数组 z[ k]中

int CommonOrder(int m, int n, int x[ ] , int y[ ] , int z[ ])
{
	int i , j , k ; 
	for (j = 0; j <= n; j ++ ) // 初始化第 0 行
		L[0][j] = 0;
	for (i = 0; j <= m; i++ ) // 初始化第 0 列
		L[i] [0] = 0;
	for (i = 1; i<= m; i++ )
		for (j = 1; j <= n; j++ )
	if (x[i] == y[j]) { L[i][j] = L[i - 1] [j - 1] + 1; S[i][j] = 1; }
	else if (L[i][j - 1] >= L[i - 1][j] ) { L[i][j] = L[i] [j - 1]; S[i][j] = 2; }
	else {L[i][j] = L[i - 1][j]; S[i][j] = 3; }
	i = m; j = n; k = L[m] [n];
	while(i > 0 && j > 0)
	{
		if (S[i][j] == 1) { z[k] = x[i] ; k -- ; i -- ; j -- ; }
		else if (S[i][j] == 2) j -- ;
		else i -- ;
	}
	return L[m][n] ;
}

int main(void)
{
	int i,j;
	int x[10] ; 
	int y[10] ; 
	int z[10] ;
	i = CommonOrder(10,10,x,y,z) ;
	printf("%d\n",i) ;
	putchar('\n');
	for(i = 0 ; i < 10 ; i++){
		for(j = 0 ; j < 10 ; j++){
			printf("%d ",L[i][j]);
		}
		putchar('\n');
	}
	
	return 0 ;
}
运行结果:

2


0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2

网友评论

登录后评论
0/500
评论
morixinguan
+ 关注