An almost-linear time and linear space algorithm for the longest common subsequence problem

檔案

日期

2005-05-16

期刊名稱

INFORMATION PROCESSING LETTERS

摘要

There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application. (c) 2005 Elsevier B.V. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料