A Space-Efficient Algorithm for Longest Common Almost Increasing Subsequence of Two Sequences

Abstract

Let $A$ and $B$ be two number sequences of length $n$ and $m$, respectively, where $m\le n$. Given a positive number $\hat{I}´$, a common almost increasing sequence $s_1\dots s_k$ is a common subsequence for both $A$ and $B$ such that for all $2\le i\le k$, $s_i+\hat{I}´>{\max }_{1\le j<i}{s}_j$. The LCaIS problem seeks to find the longest common almost increasing subsequence (LCaIS) of $A$ and $B$. An LCaIS can be computed in $O(nm\ell )$ time and $O(nm)$ space [Ta, Shieh, Lu (TCS 2021)], where $\ell$ is the length of the LCaIS of $A$ and $B$. In this paper we first give an $O(nm\ell )$-time and $O(n+m\ell )$-space algorithm to find LCaIS, which improves the space complexity. We then design an $O((n+m)\log n+\mathcal{M}\log \mathcal{M}+\mathcal{C}\ell )$-time and $O(\mathcal{M}(\ell +\log \mathcal{M}))$-space algorithm, which is faster when the number of matching pairs $\mathcal{M}$ and the number of compatible matching pairs $\mathcal{C}$ are in $o(nm/\log m)$.