|
|||||
|
|
| 最长公共子充列问题的改进快速算法 | |
| 引用本文： | 李欣,舒风笛.最长公共子充列问题的改进快速算法[J].计算机应用研究,2000,17(2):28-30. |
| 作者姓名： | 李欣 舒风笛 |
| 作者单位： | [1]北京大学软件工程实验室 [2]武汉大学计科系 |
| 摘 要： | 现在几个最常用的解决最长公共子序列（ＬＣＳ）问题的算法的时间复杂度分别是Ｏ（ｐｎ），Ｏ（ｎ（ｍｐ））。这里Ｍ、ｎ为两个待比较字符串的长度，Ｐ是最长公共子串的长度。给出一种时间复杂度为Ｏ（ｐ（ｍｐ）），空间复杂度为Ｏ（ｍ＋ｎ）的算法。与以前的算法相比，不管在Ｐ〈〈ｍ的情况下，还是在Ｐ接近Ｍ时，这种算法都有更快的速度。 |
| 关 键 词： | 最长公共子序列 算法 差分压缩算法 字符串 |
| 修稿时间： | 1999年7月16日 |
| 本文献已被 CNKI 维普 等数据库收录！ | |