Faster algorithms for computing longest common increasing subsequences

We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths n and m  , where m⩾nm⩾n, we present an algorithm with an output-dependent expected running time of O((m+nℓ)loglogσ+Sort) and O(m)O(m) space, where ℓ is the length of an LCIS, σ is the size of the alphabet, and Sort   is the time to sort each input sequence. For k⩾3k⩾3 length-n sequences we present an algorithm which improves the previous best bound by more than a factor k   for many inputs. In both cases, our algorithms are conceptually quite simple but rely on existing sophisticated data structures. Finally, we introduce the problem of longest common weakly-increasing (or non-decreasing) subsequences (LCWIS), for which we present an O(min{m+nlogn,mloglogm})-time algorithm for the 3-letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets.