• / 22
  • 下载费用:13 金币  

国家集训队2003论文集饶向荣

关 键 词:
国家集训队论文集 国家集训队2003论文集 国家集训队论文 2003集训队
资源描述:
病毒的DNA 长沙长郡中学 饶向荣 ———剖析一道字符匹配问题解析过程 题目描述题目描述 有一种奇特的病毒,它的DNA序列是环状的,而一般的生 物的DNA都是线状的,且由科学家发现:生物被此种病毒侵袭的 可能性与生物和病毒的DNA序列最大公共长度有关,由于病毒是 环状的,所以它可以循环重复的匹配。科学家们经过大量的试验 发现:如果生物和病毒DNA序列的最大公共部分的长度还没有病 毒的DNA长,病毒是无法安身的,也就是说这个生物被侵染的几 率是0,否则,最长公共部分的长度和被侵染的几率满足下面的 关系式: 生物被侵染几率=最大公共部分长度 / 生物DNA长度。 任务 现在已知病毒的DNA序列和某生物的DNA序列,你必须求出 此生物被侵染的几率是多少。 题目描述题目描述 数据范围 病毒的DNA序列长度〈=1000,生物DNA序列长度〈=105。 样例 病毒的DNA序列(环状)为abc,生物的DNA序列为 abbcabcabb,那么它们的最长的公共长度为7,最长公共部分为 红色部分:bcabcab。 分析和求解分析和求解 设A为病毒的环状DNA字串,A的长度为N。 设B为生物的线状DNA字串,B的长度为M。 那么题目所求:环串A和线串B的最大可循环公共子 串长度。 设f [i, j] 表示以线串B的第i位和环串A的第j位结 尾的最大公共子串的长度。 根据平时的解题经验,很容易想到用动态规划来解此类求 公共最大长度的题目,而且稍加分析就可设计相应的动态规 划: 分析和求解分析和求解 最后的答案: 空间复杂度为O(N)。 那么动态转移方程: 分析和求解分析和求解 经过分析,不必求出依次所有的f [i, j] ,只有当 B[i]=A[j]时,才有必要求f [i, j],其余的f值全为0。 又因为A,B中的字符只有[‘a’’z’,’A’’Z’],那么 只需在开始时用链表记录‘a’’z’,’A’’Z’出现的位置 ,动态规划的过程中就可以实现这个优化。 优化: 时间复杂度:O(M*N)。n=k时,也就是从i位置起, 可匹配到的最大位置不小于k,就可以直接从k+1位开始往后逐 字比较求Q[i]。 但这样就存在两个问题: 1. 怎么确定Q[i]+i=k呢? 2. 如果Q[i]+i=k-i+1时:Q[i]+i=k。只需从k+1向后逐字比较,就可 求出Q[i]。 dcdcdccbcabcC L dcdcdccbcabc abcdabddcdcdccbacabdB kji i-j+1k-j+1 k-i+1 所以,关键在L的计算上。 分析和求解分析和求解 L的值仅由i-j+1和C确定。 设T[x](1=x=n),表示从C的x位置起和C匹配的最大长度。 那么求解R的过程中,对B中任何位置i和对应的j,T[i-j+1]就 相当于要求的L。 dcdcdccbcabcC L dcdcdccbcabc abcdabddcdcdccbacabdB k i-j+1 ji k-j+1 k-i+1 =T[i - j+1] T T的求解的求解 接下来,求解T: 其实T的计算和Q的计算本质上是一样:都要求从一个字串 的每个位置起和C可匹配的最大长度。 Q[i]可通过T[1n]和适当比较算出来,而T[x]则可通过T[1x -1]和适当的比较求出来。 那么计算T[x]的时间复杂度:O(N)。 复杂度分析复杂度分析 此算法的总时间复杂度 =匹配的时间复杂度+计算T[x]的时间复杂度 =O(M+N)。 效率上得到了极大的提高。 问题圆满解决! 上面的解决方式,看起来与KMP十分的相似,但实际上透 彻的理解后,还是有很大的区别的。此解法主要是借鉴KMP的 思想和特点提出的,而不是生搬硬套。 回顾解题过程回顾解题过程 下面回顾整个解题的过程: 1.先考虑动态规划,行不通! 2.分析问题,发现问题要求长度不小于N的公共部分,这是此题 转化的关键条件。 3.求解分解为L[i]和R[i] 。 4.精简R[i]的求解,求相应的Q[i]。 5.灵活运用KMP解题思路和特点,设计出T数组,使得匹配的时 间复杂度降为O(M)。这部分是圆满解决此问题的关键。 总结总结 上面Q[i]的求解思路具有一定的可推广性,对于某些字符 串匹配问题可以类似的寻求问题的解决方法。 上面讲解的题目比较的简单,只是希望大家着重注意解题 的思路,但愿能够给大家一点启发。从此题的解决上,也发现 解题时要牢记以下几点: •需要全面分析问题,抓住问题的关键 •要有一定的知识积累量,必须牢固掌握基础知识 •要有灵活变通运用的能力 谢谢谢谢
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:国家集训队2003论文集饶向荣
链接地址:https://www.maidoc.com/p-15451199.html

当前资源信息

天天向上

编号: 20181010025320585282

类型: 共享资源

格式: PPT

大小: 276.00KB

上传时间: 2019-09-22

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 

本站提供办公文档学习资料考试资料文档下载


收起
展开