O(nloglogn) Algorithm for LCWIS over 3 Letters
Yong Gui · 2008
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 sophisticated data structures,bounded heap and van Emde Boes tree. The time and space complexity of our algorithm is O(nloglogn) and O(n),both of which is the best so forth.