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

and

, where $m\ge n$ , we present an algorithm with an output-dependent expected running time of $O((m+n\ell) \log\log \sigma + \mathit{Sort})$ and

space, where $\ell$ is the length of a LCIS, $\sigma$ is the size of the alphabet, and $\mathit{Sort}$ is the time to sort each input sequence.For $k\ge 3$ length-

sequences we present an algorithm running time $O(\min\{kr^2,r\log^{k-1}r\}+\mathit{Sort})$ , which improves the previous best bound by more than a factor

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.

Abstract: