文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 最长公共子序列
侵权投诉

最长公共子序列

最长公共子序列

姓名:冯小龙 学号: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]

第1页

热门文档

相关文档

  • 基于位运算的最长公共子序列算法

    基于位运算的最长公共子序列算法_理学_高等教育_教育专区。基于位运算的最长公共子序列算法IOI2006 国家集训队作业:研究报告 浙江 唐文斌 基于位运算的最长公共子...

  • 最长公共子序列问题

    最长公共子序列问题_工学_高等教育_教育专区。最长公共子序列问题2.3 最长公共子序列问题 和前面讲的有所区别,这个问题的不涉及走向。很经典的动态规划问题。 例...

  • 最长公共子序列问题

    由此可见,2 个序列的最长公共子序列包含了这 2 个序列的前缀的最长公共子 序列。 1 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 ...

  • 3788最长公共子序列---连续

    3788最长公共子序列---连续_数学_自然科学_专业资料。Description 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。 Input 输入若干组数据。字符...

  • 最长公共子序列求解

    最长公共子序列(longest common subsequence) 1 问题描述: 最长公共子序列问题(longest common subsequence problem) 找出两个字符串中共同的最长子序列 输入:两个...

  • 最长公共子序列

    最长公共子序列, 英文缩写为 LCS (Longest Common Subsequence) 其定义是, 。 一个数列?S?, 如果分别是两个或多个已知数列的子序列, 且是所有符合此条件序列...

  • 最长公共子序列算法LCS

    最长公共子序列算法LCS_电脑基础知识_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 最长公共子序列算法LCS_电脑基础知识_IT/计算机_专业资料。最长...

  • 实验二 最长公共子序列问题

    实验二 最长公共子序列问题 一、实验目的: 1、 理解动态规划算法的概念; 2、 掌握动态规划算法的基本要素; 3、 掌握设计动态规划算法的步骤; 4、 通过应用范例...

  • 【论文】最长公共子序列算法在文字录入测试中的应用

    通过检测Word文件中的关键字,可以测试出考生操作的大概结果。但是很不准确。利用最长公共子序列算法进行文字录入测试,可以很好地解决这一问题。...

  • 最长公共子序列实验报告

    而最长公共子串(要求连 续)和最长公共子序列是不同的。 最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度” ,即它 们的雷同程度,从而...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email