NYOJ 36

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

NYOJ 36

哈沙给 2012-04-13 09:06:00 浏览406
展开阅读全文

最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。简而言之,百度知道、百度百科都用得上。

 
算法

  动态规划的一个计算两个序列的最长公共子序列的方法如下:
  以两个序列 X、Y 为例子:
  设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有:
  f[1][1] = same(1,1);
  f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}
  其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”,否则为“0”。
  此时,f[j]中最大的数便是 X 和 Y 的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。
  该算法的空间、时间复杂度均为O(n^2),经过优化后,空间复杂度可为O(n)。

 

 


动态规划法

经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。

为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。

 

考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bn-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:

(1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;(肯定是,因为最后一个若相等,则该字符必在LCS中)

(2) 如果am-1!=bn-1,则若zk-1!=am-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列;

(3) 如果am-1!=bn-1,则若zk-1!=bn-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列。

这样,在找A和B的公共子序列时,如有am-1=bn-1,则进一步解决一个子问题,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一个最长公共子序列;如果am-1!=bn-1,则要解决两个子问题,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列。

 

最长公共子序列
时间限制:3000 ms | 内存限制:65535 KB
难度:3
描述
咱们就不拐弯抹角了,如题,需要你做的就是写一个程序,得出最长公共子序列。
tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为
LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
输入
第一行给出一个整数N(0<N<100)表示待测数据组数
接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000.
输出
每组测试数据输出一个整数,表示最长公共子序列长度。每组结果占一行。
样例输入
2
asdf
adfsd
123abc
abc123abc
样例输出
3
6

 

 

非连续
#include <stdio.h>
#include <string.h>
#define N 100
int dp[N+1][N+1];
char str1[N],str2[N];
int max(int a,int b)
{
if(a>b)
return a;
return b;
}
int LCSL(int len1,int len2)
{
int i,j;
int len=max(len1,len2);
for(i=0;i<=len;i++)
{
dp[i][0]=0;//等于是说其中一个字符串长度为0,则LCSL必为0
dp[0][i]=0;
  }
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
if(str1[i-1]==str2[j-1])
   dp[i][j]=dp[i-1][j-1]+1;
else
   dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
return dp[len1][len2];
}
int main()
  {
int m;int len1,len2;
scanf("%d",&m);
while(m--)
{
scanf("%s%s",str1,str2);
int len1=strlen(str1);
int len2=strlen(str2);
printf("%d\n",LCSL(len1,len2));   
}   
return 0;
}

网友评论

登录后评论
0/500
评论
哈沙给
+ 关注