Faster Algorithms for Computing Longest Common Increasing Subsequences

Abstract

We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths m and n , where m >= n, we present an algorithm with an output-dependent expected running time of O((m + n l) log log sigma + Sort) and O(m) space, where l is the length of an LCIS, sigma is the size of the alphabet, and 'Sort' is the time to sort each input sequence.

For k >= 3 length-n sequences we present an algorithm running time O(min{k r^2, r log^{k-1} r} + Sort), 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(m + n log n) 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.