3字符最长公共弱递增子串的O（nloglogn）算法

计算机科学 ›› 2008, Vol. 35 ›› Issue (3): 264-266.

3字符最长公共弱递增子串的O（nloglogn）算法

归泳昆

复旦大学上海智能信息处理重点实验室,上海200433

出版日期:2018-11-16 发布日期:2018-11-16

GUI Yong-Kun （Shanghai Key Library of Intelligent Information Processing, Fudan University, Shanghai 200433）

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 最长公共子串（LCS）和最长递增子串（LIS）是两个非常经典的基础算法问题，并且在生物信息学中已有重要应用。2006年，Brodal等人提出了最长公共弱递增字串问题（LCWIS），并且给出了2字符字母表上线性时间算法和3字符字母表上O（nlogn）时间的算法。本文中，我们提出了一种新的在3字符字母表上寻找最长公共弱递增子串（LC-WIS）的算法。该算法利用了两个成熟的数据结构：约束堆（Bounded heap）和van Emde Boas树。我们算法的时间复杂度是O（nloglogn），空间复杂度为O（n

关键词: 约束堆 van Emde Boas树最长弱递增公共子串生物信息学

Abstract: Longest common subsequence（LCS） and longest increasing subsequence（LIS） are two classic algorithm problems. Both of them have important applications in bioinformatics. In 2006, Brodal et al. proposed another string problem called longest common weakly inc

Key words: Bounded heap, van Erode Boer Tree, LCWIS, Bioinformatics

归泳昆. 3字符最长公共弱递增子串的O（nloglogn）算法[J]. 计算机科学, 2008, 35(3): 264-266. https://doi.org/

GUI Yong-Kun （Shanghai Key Library of Intelligent Information Processing, Fudan University, Shanghai 200433）. [J]. Computer Science, 2008, 35(3): 264-266. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed