最长公共子序列（动态规划）

Simone_chou

浏览: 192870 次
性别:
来自: 广州

最近访客更多访客>>

xiaohuih1985

小橙子

ybj316

努力成为Java大神

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

NYOJ

最长公共子序列

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述

咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。
tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

输入

第一行给出一个整数N(0<N<100)表示待测数据组数
接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

输出

每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

样例输入

2
asdf
adfsd
123abc
abc123abc

样例输出

3
6

思路：

如图所示为最长公共子序列。（子序列是不连续的，子串是连续的）

现有两个序列X={x₁,x₂,x_3，...x_i}，Y={y₁,y₂,y_3，....，y_i}，

设有C[i,j]: 保存X_i与Y_j的最长公共子序列（LFS）的长度。

演示过程如图所示，如果X_i,Yi相同，则取对角线的数+1；

如果X_i,Yi不相同，则对比上面或左边的数，取最大值+1；

根据下面的演示其实可以发现C[i,j]一直保存着当前(X_i,Y_i)的最大子序列长度。

(1) 当X[i]=Y[j]时， C(i, j)=C(i-1, j-1) 1 。证明很简单。

(2) 当X[i]!=Y[j]时，说明此事X[0...i]和Y[0...j]的最长公共子序列中绝对不可能同时含有X[i]和Y[j]。那么公共子序列可能以X[i]结尾，可能以Y[j]结尾，可以末尾都不含有X[i]或Y[j]。

因此 C(i, j)= MAX{Ci-1 , j), C(i, j-1)}

Explain in detail：

事实上，最长公共子序列问题也有最优子结构性质。

记：

Xi = <x1,x2,x3,....xi> 即X序列的前i个字符（1<= i <= m）(前缀)

Yj = <y1,y2,y3,....yi> 即Y序列的前j个字符（1<= j <= m）(前缀)

假定Z = <z1,z2,z3,...zk>是LCS（X,Y)中的一个。

·若xm = yn（最后一个字符相同），则不难用反正法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有zk = xm = yn，且显然有Zk-1∈LCS(Xm-1,Yn-1)，即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时，问题化归成求Xm-1与Yn-1的LCS（LCS(X,Y)）的长度等于LCS(Xm-1,Yn-1)的长度加1）。

·若xm≠yn，则亦不难用反证法证明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立，若zk≠xm则有Z∈LCS(Xm-1 , Y)；类似的，若zk≠yn 则有Z∈LCS(X , Yn-1)。此时，问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为：max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。

由于上述当xm≠yn的情况中，求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度，这两个问题不是相互独立的：两者都需要求LCS(Xm-1，Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。

Wrong：

#include<stdio.h>
#include<string.h>
int main()
{
	int N,i,j;
	int alen,blen;
	char a[1005];
	char b[1005];
	char same[1005][1005];
//手抽这里写错了 应该是int类型……
	scanf("%d",&N);
	while(N--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(same,0,sizeof(same));
		scanf("%s",a);
		scanf("%s",b);
		alen=strlen(a);
		blen=strlen(b);
		for(i=1;i<=alen;i++)
		 for(j=1;j<=blen;j++)
		{
			if(a[i-1]==b[j-1]) same[i][j]=same[i-1][j-1]+1;
//这里的字符要-1
			else same[i][j]=(same[i-1][j]>same[i][j-1]?same[i-1][j]:same[i][j-1]);
		}
	    printf("%d\n",same[alen][blen]);
	}
	return 0;
}

AC：

#include<stdio.h>
#include<string.h>
int main()
{
	int N,i,j;
	int alen,blen;
	char a[1005];
	char b[1005];
	int same[1005][1005];
	scanf("%d",&N);
	while(N--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(same,0,sizeof(same));
		scanf("%s",a);
		scanf("%s",b);
		alen=strlen(a);
		blen=strlen(b);
		for(i=1;i<=alen;i++)
		 for(j=1;j<=blen;j++)
		{
			if(a[i-1]==b[j-1]) same[i][j]=same[i-1][j-1]+1;
			else same[i][j]=(same[i-1][j]>same[i][j-1]?same[i-1][j]:same[i][j-1]);
		}
	    printf("%d\n",same[alen][blen]);
	}
	return 0;
}

总结：

吸收一下别人的解法。要静下心来慢慢理解。

http://blog.csdn.net/v_july_v/article/details/6695482