最长公共子序列问题的改进快速算法

被引：9

作者：

李欣

舒风笛

机构：

[1] 北京大学软件工程实验室!北京１００８７１

[2] 武汉大学计科系!武汉４３００７２

来源：

计算机应用研究 | 2000年 / 02期

关键词：

最长公共子序列; LCS;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：28 / 30

页数：3