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

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

O(nloglogn) Algorithm for LCWIS over 3 Letters

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 increasing substring(LCWIS) problem,and they gave a linear time algorithm on 2-letter LCWIS problem,and a O(nlogn) time algorithm on 3-letter LCWIS problem. In our paper,we present a new algorithm on 3-letter LCWIS problem. This algorithm relies on existing sop...