## 1 Introduction  
In this paper, we consider a generalized longest common subsequence problem. The longest common subsequence (LCS) problem is a well-known measurement for computing the similarity of two strings. This problem can be widely applied in diverse areas, such as file comparison, pattern matching and computational biology [1]. A sequence is an ordered list of characters over an alphabet, \(\sum\). A subsequence of a sequence, \(X,\) is obtained by deleting zero or more characters (not necessarily contiguous) from \(X\). A substring of a sequence, \(X\), is a subsequence of successive characters within \(X\). For a given sequence, \(X=x_{1}x_{2}\cdots x_{n}\), of length \(n\), the \(i\)th character of \(X\) is denoted, \(x_{i}\in\sum\), for any \(i=1,\cdots,n\). A substring of \(X\) from position \(i\) to \(j\) can be denoted as \(X[i:j]=x_{i}x_{i+1}\cdots x_{j}\). A substring, \(X[i:j]\), is called a prefix of \(X\) if \(i=1\) and a suffix of \(X\) if \(j=n\). Given two sequences, \(X\) and \(Y\), the LCS problem is finding a subsequence of \(X\) and \(Y\) whose length is the longest among all common subsequences of the two given sequences. For some biological applications, some constraints must be applied to the LCS problem. These types of variants of the LCS problem are called constrained LCS (CLCS) problems [2]. A recent variant of the LCS problem, which was first addressed in [2], has received considerable attention. The most cited algorithms solve the CLCS problem based on dynamic programming algorithms. Some improved algorithms have also been proposed in [3, 4]. The LCS and CLCS problems on indeterminate strings were also discussed in [4]. A bit-parallel algorithm for solving the CLCS problem was proposed in [3]. The problem was extended to have weighted constraints, a more generalized problem, in [5]. A variant of the CLCS problem with multiple constraints, the restricted LCS problem, which excludes the given constraint as a subsequence of the answer, was proposed in [6]. This restricted LCS problem becomes non-deterministic polynomial-time hard (NP-hard) when the number of constraints is not fixed [6]. Recently, [PERSON] and [PERSON] [7] proposed a more generalized form of the CLCS problem, the generalized-constrained-LCS (GC-LCS) problem. For the two input sequences, \(X\) and \(Y\), of lengths \(n\) and \(m\), respectively, and a constraint string, \(P\), of length \(r\), the GC-LCS problem is a set of four problems that find the LCS of \(X\) and \(Y\) that includes/excludes \(P\) as a subsequence/substring. The four generalized constrained LCSs are summarized in Table 1[7]. We will discuss the STR-EC-LCS problem in this paper. We found that a previously proposed dynamic programming algorithm for the STR-EC-LCS problem [7] cannot correctly solve the problem. Let \(L(i,j,k)\) denote the length of an LCS of \(X[1:i]\) and \(Y[1:j]\), excluding \(P[1:k]\) as a substring. [PERSON] and [PERSON] gave a recursive Formula (1) for computing \(L(i,j,k)\) as follows. \[L(i,j,k)=\left\{ \begin{array}{ll}L(i-1,j-1,k)&\mbox{if }k=1\mbox{ and }x_{i}=y_{j}=p_{k},\\ 1+\max\{L(i-1,j-1,k-1),L(i-1,j-1,k)\}&\mbox{if }k\geq 2\mbox{ and }x_{i}=y_{j}=p_{k},\\ 1+L(i-1,j-1,k)&\mbox{if }x_{i}=y_{j}\mbox{ and }(k>0\mbox{ and }x_{i}\
eq p_{k}), \\ \max\{L(i-1,j,k),L(i,j-1,k)\}&\mbox{if }x_{i}\
eq y_{j}\end{array} \right. \tag{1}\] \begin{table}
\begin{tabular}{l l l} \hline \hline
**Problem** & **Input** & **Output** \\ \hline SEQ-IC-LCS & \(X\), \(Y\), and \(P\) & The LCS of \(X\) and \(Y\) that includes \(P\) as a subsequence \\ STR-IC-LCS & \(X\), \(Y\), and \(P\) & The LCS of \(X\) and \(Y\) that includes \(P\) as a substring \\ SEQ-EC-LCS & \(X\), \(Y\), and \(P\) & The LCS of \(X\) and \(Y\) that includes \(P\) as a subsequence \\ STR-EC-LCS & \(X\), \(Y\), and \(P\) & The LCS of \(X\) and \(Y\) that includes \(P\) as a substring \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The generalized-constrained-longest common subsequence (GC-LCS) problems. STR-EC, string-excluding.