- 1、本文档共8页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
;序列:由若干字符构成的字符串或者文本。
子序列:一个序列删去若干元素后得到的序列。
公共子序列:给定两个序列X和Y,若序列Z既是X的子序列又是Y的子序列,称Z是序列X和Y的公共子序列。
最长公共子序列(LongestCommonSubsequence,LCS):公共子序列中长度最长的子序列。;例如:
X=(B,D,A,B,A,C)
Y=(B,A,D,B,C,D,A);判断:对于两个序列X和Y,它们的最长公共子序列可能不唯一,但最长公共子序列的长度是唯一的。;穷举法:
对于X的每一个子序列,验证它是否是Y的子序列。
X有2m个子序列。
每个子序列需要O(n)的时间来验证它是否是Y的子序列。;是否可以用动态规划求解最长公共子序列问题呢?;最优子结构性质分析:
问题的最优值与两个序列的长度有关。;序列Xm=(x1,x2,…,xm),定义Xm的第i个前缀为:Xi=(x1,x2,…,xi),i=0,1,2…m;
您可能关注的文档
- 算法设计与分析 教学大纲 许瑾晨.pdf
- 算法设计与分析 课程大纲 许瑾晨.docx
- 算法设计与分析 课件 0-算法导论.pptx
- 算法设计与分析 课件 1.0-算法评价-序.pptx
- 算法设计与分析 课件 1.1-算法基础.pptx
- 算法设计与分析 课件 1.2.0-算法分析准则.pptx
- 算法设计与分析 课件 1.2.1-算法分析准则 - 正确性.pptx
- 算法设计与分析 课件 1.2.2-算法分析准则 - 时间复杂度.pptx
- 算法设计与分析 课件 1.2.3-算法分析准则 - 时间复杂度 - 渐近分析及符号表示.pptx
- 算法设计与分析 课件 1.2.4-算法分析准则 - 时间复杂度 - 非递归.pptx
- 人教版九年级英语全一册单元速记•巧练Unit13【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit9【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit11【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit14【单元测试·提升卷】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit8【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit4【单元测试·提升卷】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit13【单元测试·基础卷】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit7【速记清单】(原卷版+解析).docx
- 苏教版五年级上册数学分层作业设计 2.2 三角形的面积(附答案).docx
- 人教版九年级英语全一册单元速记•巧练Unit12【单元测试·基础卷】(原卷版+解析).docx
最近下载
- 2024年中国石油秋季招聘通用能力考试笔试备考试题及答案解析.docx
- 第一课 教室盆栽我做主—盆栽养护 课件 浙科版综合实践活动四年级上册.pptx
- 医疗安全(不良)事件根本原因分析法活动指南.pdf VIP
- 2023年中考押题预测卷02(杭州卷)-英语(考试版)A4.docx
- 于品 清华丘班数学分析讲义.pdf VIP
- 金融风险管理(中央财经大学)中国大学MOOC(慕课)章节测验试题(答案).pdf
- 一年一度喜剧大赛江东鸣《先生请出山》完整台词.docx VIP
- 党员立足本职岗位发挥党员先锋引领作用发言稿.doc VIP
- 《机床电气控制》M7130型卧轴矩台平面磨床的电气控制.pdf VIP
- Unit 4 Period 4 Developing Ideas 课件-高一上学期英语课件(外研社2019必修第一册).pptx
文档评论(0)