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

• 作者: 李欣 舒风笛
• 来源期刊: 计算机应用研究
• 关键词: 最长公共子序列 LCS
• 年，卷（期）: 2000,（2）
• 所属期刊栏目: 研究探讨
• 页码范围: 28-30
• 页数: 3页
• 分类号: TP3
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2000.02.011

摘要

现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n为两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p)),空间复杂度为O(m+n)的算法.与以前的算法相比,不管在p<<m的情况下,还是在p接近m时,这种算法都有更快的速度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李欣	北京大学软件工程实验室	64	442	12.0	19.0
2	舒风笛	武汉大学计科系	5	69	3.0	5.0