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

Let $A$ and $B$ be two number sequences of length $n$ and $m$, respectively, where $m\le n$. Given a positive number $\delta$, 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+\delta >{\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\mathrm{\ell })$ time and $O(nm)$ space [Ta, Shieh, Lu (TCS 2021)], where $\mathrm{\ell }$ is the length of the LCaIS of $A$ and $B$. In this paper we first give an $O(nm\mathrm{\ell })$-time and $O(n+m\mathrm{\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}\mathrm{\ell })$-time and $O(\mathcal{M}(\mathrm{\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\mathrm{/}\log m)$.