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