利用矩阵搜索求所有最长公共子序列的算法

• 作者: 宫洁卿
• 来源期刊: 安徽工程科技学院学报（自然科学版）
• 学科: 工学
• 关键词: 最长公共子序列(LCS) 矩阵搜索 算法
• 年，卷（期）: 2008,（4）
• 页码范围: 52-56
• 页数: 5页
• 分类号: TP301.6
• 字数: 5216字
• 语种: 中文
• DOI: 10.3969/j.issn.2095-0977.2008.04.014

摘要

利用动态规划法求出二维数组的情况下,使用矩阵搜索的方法求出所有分支,从而求出所有最长公共子序列的算法.该算法将通常认为的指数量级的时问复杂度降低到了max{O(cmn).O(ck)}.随后对此算法的正确性以及效率做了证明.