Faster Space-Efficient STR-IC-LCS Computation

Abstract

One of the most fundamental method for comparing two given strings $A$ and $B$ is the longest common subsequence (LCS), where the task is to find (the length) of an LCS of $A$ and $B$. In this paper, we deal with the STR-IC-LCS problem which is one of the constrained LCS problems proposed by Chen and Chao [J. Comb. Optim, 2011]. A string $Z$ is said to be an STR-IC-LCS of three given strings $A$, $B$, and $P$, if $Z$ is a longest string satisfying that (1) $Z$ includes $P$ as a substring and (2) $Z$ is a common subsequence of $A$ and $B$. We present three efficient algorithms for this problem: First, we begin with a space-efficient solution which computes the length of an STR-IC-LCS in $O(n^2)$ time and $O((\ell +1)(n-\ell +1))$ space, where $\ell$ is the length of an LCS of $A$ and $B$ of length $n$. When $\ell =O(1)$ or $n-\ell =O(1)$, then this algorithm uses only linear $O(n)$ space. Second, we present a faster algorithm that works in $O(nr/\log r+n(n-\ell +1))$ time, where $r$ is the length of $P$, while retaining the $O((\ell +1)(n-\ell +1))$ space efficiency. Third, we give an alternative algorithm that runs in $O(nr/\log r+n(n-{\ell }^{\prime }+1))$ time with $O(({\ell }^{\prime }+1)(n-{\ell }^{\prime }+1))$ space, where ${\ell }^{\prime }$ denotes the STR-IC-LCS length for input strings $A$, $B$, and $P$.

This is a full version of "Space-Efficient STR-IC-LCS Computation" presented at SOFSEM 2023

References in corpus (1)

• A Simple Algorithm for the Constrained Sequence Problems