RookiePeng

原创 Python实现子序列系列问题——最长公共子序列

题目描述：给定两个序列X={x1, x2, x3, ...xm}和Y={y1, y2, y3, ... yn}, 求X和Y的最长公共子序列。分析：如果采用暴力搜索的方法的话，需要穷举X的所有子序列然后分别和Y的所有子序列进行比较，从而筛选出LCS。X共有2^m个子序列，所以暴力搜索的话复杂度肯定是指数阶的，显然不实用。那我们能否通过X和Y的前缀子序列的结果分析推导出X和Y的子序列呢？    假设X...