  The longest common subsequence (LCS) problem is a central problem in
stringology that finds the longest common subsequence of given two strings $A$
and $B$. More recently, a set of four constrained LCS problems (called
generalized constrained LCS problem) were proposed by Chen and Chao [J. Comb.
Optim, 2011]. In this paper, we consider the substring-excluding constrained
LCS (STR-EC-LCS) problem. A string $Z$ is said to be an STR-EC-LCS of two given
strings $A$ and $B$ excluding $P$ if, $Z$ is one of the longest common
subsequences of $A$ and $B$ that does not contain $P$ as a substring. Wang et
al. proposed a dynamic programming solution which computes an STR-EC-LCS in
$O(mnr)$ time and space where $m = |A|, n = |B|, r = |P|$ [Inf. Process. Lett.,
2013]. In this paper, we show a new solution for the STR-EC-LCS problem. Our
algorithm computes an STR-EC-LCS in $O(n|\Sigma| + (L+1)(m-L+1)r)$ time where
$|\Sigma| \leq \min\{m, n\}$ denotes the set of distinct characters occurring
in both $A$ and $B$, and $L$ is the length of the STR-EC-LCS. This algorithm is
faster than the $O(mnr)$-time algorithm for short/long STR-EC-LCS (namely, $L
\in O(1)$ or $m-L \in O(1)$), and is at least as efficient as the $O(mnr)$-time
algorithm for all cases.
