  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'+1))$ time with
$O((\ell'+1)(n-\ell'+1))$ space, where $\ell'$ denotes the STR-IC-LCS length
for input strings $A$, $B$, and $P$.
