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

J. Y. Guo*, F. K. Hwang

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

7 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
頁(從 - 到)131-135
頁數5
期刊Information Processing Letters
94
發行號3
DOIs
出版狀態已發佈 - 2005 五月 16

ASJC Scopus subject areas

  • 理論電腦科學
  • 訊號處理
  • 資訊系統
  • 電腦科學應用

指紋

深入研究「An almost-linear time and linear space algorithm for the longest common subsequence problem」主題。共同形成了獨特的指紋。

引用此