  The constrained LCS problem asks one to find a longest common subsequence of
two input strings $A$ and $B$ with some constraints. The STR-IC-LCS problem is
a variant of the constrained LCS problem, where the solution must include a
given constraint string $C$ as a substring. Given two strings $A$ and $B$ of
respective lengths $M$ and $N$, and a constraint string $C$ of length at most
$\min\{M, N\}$, the best known algorithm for the STR-IC-LCS problem, proposed
by Deorowicz~({\em Inf. Process. Lett.}, 11:423--426, 2012), runs in $O(MN)$
time. In this work, we present an $O(mN + nM)$-time solution to the STR-IC-LCS
problem, where $m$ and $n$ denote the sizes of the run-length encodings of $A$
and $B$, respectively. Since $m \leq M$ and $n \leq N$ always hold, our
algorithm is always as fast as Deorowicz's algorithm, and is faster when input
strings are compressible via RLE.
