论文部分内容阅读
现在几个最常用的解决最长公共子序列（ＬＣＳ）问题的算法的时间复杂度分别是O（ｐｎ），O（ｎ（ｍ－ｐ））．这里ｍ、ｎ两个待比较字符串的长度，ｐ是最长公共子串的长度．给出一种时间复杂度为Ｏ（ｐ（ｍ－ｐ））；空间复杂度为Ｏ（ｍ＋ｎ）的算法．与以前的算法相比；不管在ｐ＜＜ｍ的情况下，还是在ｐ接近ｍ时，这种算法都有更快的速度．