`
Simone_chou
  • 浏览: 182783 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

最长公共子序列(动态规划)

    博客分类:
  • 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={x1,x2,x3,...xi},Y={y1,y2,y3,....,yi},

     设有C[i,j]: 保存Xi与Yj的最长公共子序列(LFS)的长度。

 

       

   

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

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

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

   (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

  • 大小: 7.9 KB
  • 大小: 69.2 KB
  • 大小: 13.2 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics