1、 病毒的DNA剖析一道字符匹配问题解析过程长沙长郡中学 饶向荣题目描述有一 奇特的病毒， 的种 它 DNA序列是 的，而一般环状的生物的DNA都是 的，且由科 家 ：生物被此 病毒线状 学 发现 种侵 的可能性 生物和病毒的袭 与 DNA序列最大公共 度有 ，由长 关于病毒是 的，所以 可以循 重 的匹配。科 家 大环状 它 环 复 学 们经过量的 ：如果生物和病毒试验发现 DNA序列的最大公共部分的长度 有病毒的还没 DNA ，病毒是无法安身的，也就是 生长 说这个物被侵染的几率是0，否 ，最 公共部分的 度和被侵染的几则 长 长率 足下面的 系式：满 关生物被侵染几率=最大公共部分 度 长
2、 / 生物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
3、的第j位 尾的最大公共子串的 度。结 长根据平 的解 ，很容易想到用 解此时 题经验 动态规划来 类求公共最大 度的 目，而且稍加分析就可 相 的长 题 设计 应 动态：规划分析和求解)1,1,max( njmijifAns 最后的答案：空 度间复杂 为O(N)。01,1,11,11,1,iBjAjiBjAnifnjiBjAjifjif 且且那 移方程：么动态转分析和求解分析，不必求出依次所有的经过 f i, j ，只有当Bi=Aj ，才有必要求时 f i, j，其余的f 全值 为0。又因为A,B中的字符只有a.z,A.Z，那么只需在 始 用 表开 时 链 记录a.z,A.Z出 的现位置, 的
4、 程中就可以 化。动态规划 过 实现这个优优化：时间复杂度：O(M*N)。n=1000, m=105。时间复杂度太高了！分析和求解很 找到在 度上有难 时间复杂 质的 的其 的 。飞跃 它 动态规划的 症 有解 ：问题 结 没 决是否有其他的更 的 动态规划算法的时间复杂度还是没有降低。 问题转化只有最大公共子串的长度大于等于N时，才有必要计算这个长度。 a b cCac bA因 串的匹配 始位置是不 的， 一般的字符匹配为环 与是不 的。所以不 串问题 将环 A ， 串断开 设为线 C。用到 一 动态规划 条 :如 用此 运 条 ，又可以 ：此 上 一般字符转换 发现 题实际 较类匹配 ，不
5、 在于此 有 串 在 问题 题 环求解的变换如果最 公共部分 度大于 于长 长 N,那 此公共部分中 么 C中所有字符。)1,1max( MiiRiLAns 如果最大公共部分的 度 于长 N的， 可 出输 0。 只需 最大公共 度大于 于们 虑 长 N的 。况那 如果求出么 从B的第i位和C的第一位 后循 匹配的最大环度长 ,记为Ri。 abc abbcabcabbRiLi-1BiBi-1abbcabcabbbcabbcabbcabbc=52=C1Cn求出从B的第i-1位和C的最后一位 循 匹配的最大环 长度，记为Li-1。Ri的求解Ri的 求法 ：为举B中位置i，和C 后匹配到不能匹配 ， 匹为 显配的 度可 到长 达 M，那 此法的 度么 复杂 为O(M2)，复杂度有增无减！必 不必要的匹配须 虑 :如果从I 始后currency1字 ，已匹配的 度已 到开 较时 长 经达N，那 就 有必要 后 ，必有么 没 较 Ri=Ri+n+n“。abbcabcabbi i+nRi Ri+nnabc abcabc
