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