饶向荣 ———剖析一道字符匹配问题解析过程.pptVIP

病毒的DNA 长沙长郡中学 饶向荣 题目描述 题目描述 分析和求解 分析和求解 分析和求解 分析和求解 问题转化 求解的变换 R[i]的求解 Q[i]的求解 分析和求解 分析和求解 分析和求解 分析和求解 分析和求解 分析和求解 T的求解 复杂度分析 回顾解题过程 总结 谢谢 * * ———剖析一道字符匹配问题解析过程 有一种奇特的病毒，它的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=1000, m=105。 时间复杂度 太高了！ 很难找到在时间复杂度上有质的飞跃的其它的动态规划。 问题的结症没有解决： 是否有其他的更好的动态规划！ 算法的时间复杂度还是没有降低。 只有最大公共子串的长度大于等于N时，才有必要计算这个长度。 a b c C a c b A 因为环串的匹配起始位置是不定的，与一般的字符匹配问题是不同的。所以不妨先将环串A断开，设为线串C。 动态规划未用到另一条件: 如何运用此条件？ 转换思路，又可以发现：此题实际上比较类似一般字符匹配问题，不同点在于此题有环串存在！ 如果最长公共部分长度大于等于N,那么此公共部分中包含C中所有字符。 ∵如果最大公共部分的长度小于N的，直接可输出0。 ∴ 我们只需考虑最大公共长度大于等于N的情况。 那么如果求出从B的第i位和C的第一位起向后循环匹配的最大长度,记为R[i]。 abc abbcabcabb R[i] L[i-1] B[i] B[i-1] abbcabcabb abbcabcabb abbcabcabb abbcabcabb abbcabcabb abbcabcabb abbcabcabb =5 2= C[1] C[n] 再求出从B的第i-1位和C的最后一位起向前循环匹配的最大长度，记为L[i-1]。 R[i]的初步求法为： 枚举B中位置i，和C向后匹配到不能匹配为止，显然匹配的长度可达到M，那么此法的复杂度为O(M2)，复杂度有增无减！ 必须考虑避免不必要的匹配: 如果从I开始往后逐字比较时，已匹配的长度已经达到了N，那么就没有必要再往后比较了，必然有R[i]=R[i+n]+n成立。 abbcabcabb i i+n R[i] R[i+n] n abc abbcabcabb abbcabcabb 定义Q[i]表示B从位置i开始和C非循环匹配的最大长度。那么求出Q[i]，就求出了R[i]了。 R[i]那么问题等价于求Q[i]，如何求Q[i]? 一般的，到了这一步，我们希望可以通过字符匹配类问题中高效的KMP算法来求出Q[i]。 但稍加分析就会发现:KMP的匹配过程是跳动的，不便于求出所有的Q[i