1、病毒的 DNA 剖析一道字符匹配问题解析过程 长沙长郡中学 饶向荣 题目描述 有一种奇特的病毒，它的 DNA序列是环状的，而一般的生物的 DNA都是线状的，且由科学家发现：生物被此种病毒侵袭的可能性与生物和病毒的 DNA序列最大公共长度有关，由于病毒是环状的，所以它可以循环重复的匹配。科学家们经过大量的试验发现：如果生物和病毒 DNA序列的最大公共部分的长度还没有病毒的 DNA长，病毒是无法安身的，也就是说这个生物被侵染的几率是 0，否则，最长公共部分的长度和被侵染的几率满足下面的关系式： 生物被侵染几率 =最大公共部分长度 / 生物 DNA长度。 任务 现在已知病毒的 DNA序列和某生物的
2、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位结尾的最大公共子串的长度。 根据平时的解题经验，很容
3、易想到用动态规划来解此类求公共最大长度的题目，而且稍加分析就可设计相应的动态规划： 分析和求解 )1,1,m a x ( njmijifA n s 最后的答案： 空间复杂度为 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 c C a c b A 因为环串的匹配起始位置是不定的，与一般的字符匹配问题是不同的。所以不妨先将环串 A断开，设为线串 C。 动态规划未用到另一条件 : 如何运用此条件？ 转换思路，又可以发现：此题实际上比较类似一般字符匹配问题，不同点在于此题有环串存在！ 求解的变换 如果最长公共部
5、分长度大于等于 N,那么此公共部分中包含 C中所有字符。 )1,1m a x ( MiiRiLA n s 如果最大公共部分的长度小于 N的，直接可输出 0。 我们只需考虑最大公共长度大于等于 N的情况。 那么如果求出从 B的第 i位和 C的第一位 起向后循环匹配的最大长度 ,记为 Ri。 abc abbcabcabb Ri Li-1 Bi Bi-1 abbcabcabb ababcabbbbabbcabbc=5 2= C1 Cn 再求出从 B的第 i-1位和 C的最后一位起向前循环匹配的最大长度，记为 Li-1。 Ri的求解 Ri的初步求法为： 枚举 B中位置 i，和 C向后匹配到不能匹配为止，显然匹配的长度可达到 M，那么此法的复杂度为 O(M2)， 复杂度有增无减！ 必须考虑避免不必要的匹配 : 如果从 I开始往后逐字比较时，已匹配的长度已经达到了 N，那么就没有必要再往后比较了，必然有 Ri=Ri+n+n成立。 abbcabcabb i i+n Ri Ri+n n abc abcabc
