最长公共子序列
姓名:冯小龙 学号:0304110106 班级:计科1101
1.问题描述:给定的两个序列X和Y,当另一个序列Z即是X的子序列有事Y的子序列时,
称Z是X和Y的公共子序列。最长公共子序列问题即找出最长的公共子序列。
2.问题分析:设序列X={x, x, …, x}和Y={y, y, …, y}的最长公共子序列为
12m12n
Z={z, z, …, z} ,则若x= y,则z= x= y,且Z是X和Y
12km n km n k-1m-1n-1的最长公共子序列。若x≠ y且z≠x,则Z是X和Y的最长公共
m nk mm-1
子序列。若x≠ y且z≠ y,则Z是X和Y的最长公共子序列。
m nk n n-1
递归式分析:由最长公共子序列问题的最优子结构性质可知,要找出X={x,
1
x, …, x}和Y={y, y, …, y}的最长公共子序列,可按以下2m12n
方式递归地进行:
(1).当x= y时,找出X和Y的最长公共子序列,然后在其尾
m nm-1n-1
部加上x(或y);
m n
(2).当x≠ y时,必须解两个子问题:
m n
a.找出X和Y的最长公共子序列及 X和Y的最长公共子m-1n-1
序列
b.这两个公共子序列中较长者即为X和Y的最长公共子序列。
算法时间复杂度:在LSClength算法中,由于每个数组单元的计算耗费O(1)
时间,算法LSCLength耗时O(mn)。在算法LCS中,每一
次递归调用使i或j减一,因此算法的计算时间为O(m+n)。
3.算法描述:
RECURSIVE-LCS-LENGTH(X, Y, i, j)
ifi==0||j==0 return0 if X[i] == Y[j]
基于位运算的最长公共子序列算法_理学_高等教育_教育专区。基于位运算的最长公共子序列算法IOI2006 国家集训队作业:研究报告 浙江 唐文斌 基于位运算的最长公共子...
最长公共子序列问题_工学_高等教育_教育专区。最长公共子序列问题2.3 最长公共子序列问题 和前面讲的有所区别,这个问题的不涉及走向。很经典的动态规划问题。 例...
由此可见,2 个序列的最长公共子序列包含了这 2 个序列的前缀的最长公共子 序列。 1 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 ...
3788最长公共子序列---连续_数学_自然科学_专业资料。Description 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。 Input 输入若干组数据。字符...
最长公共子序列(longest common subsequence) 1 问题描述: 最长公共子序列问题(longest common subsequence problem) 找出两个字符串中共同的最长子序列 输入:两个...
最长公共子序列, 英文缩写为 LCS (Longest Common Subsequence) 其定义是, 。 一个数列?S?, 如果分别是两个或多个已知数列的子序列, 且是所有符合此条件序列...
最长公共子序列算法LCS_电脑基础知识_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 最长公共子序列算法LCS_电脑基础知识_IT/计算机_专业资料。最长...
实验二 最长公共子序列问题 一、实验目的: 1、 理解动态规划算法的概念; 2、 掌握动态规划算法的基本要素; 3、 掌握设计动态规划算法的步骤; 4、 通过应用范例...
通过检测Word文件中的关键字,可以测试出考生操作的大概结果。但是很不准确。利用最长公共子序列算法进行文字录入测试,可以很好地解决这一问题。...
而最长公共子串(要求连 续)和最长公共子序列是不同的。 最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度” ,即它 们的雷同程度,从而...
热门文档