## 2 A Simple Dynamic Programming Solution  
For the two input sequences, \(X=x_{1}x_{2}\cdots x_{n}\) and \(Y=y_{1}y_{2}\cdots y_{m}\), of lengths \(n\) and \(m\), respectively, and a constraint string, \(P=p_{1}p_{2}\cdots p_{r}\), of length \(r\), we want to find an LCS of \(X\) and \(Y\) that excludes \(P\) as a substring. In the description of our new algorithm, a function, \(\sigma\), will be mentioned frequently. For any string, \(S\), and a fixed constraint string, \(P\), the length of the longest suffix of \(S\) that is also a prefix of \(P\) is denoted by the function, \(\sigma(S)\). The function, \(\sigma\), refers to both \(P\) and \(S\). Because the string, \(S\), is a variable and the constraint string, \(P\), is fixed, the notation, \(\sigma(S)\), will not cause confusion, even though it does not reflect its dependence on \(P\). The symbol, \(\oplus\), is also used to denote string concatenation. For example, if \(P=aaba\) and \(S=aabaaab\), then substring \(aab\) is the longest suffix of \(S\) that is also a prefix of \(P\); therefore, \(\sigma(S)=3\). It is readily seen that \(S\oplus P=aabaaabaaba\). \begin{table}
\begin{tabular}{l c c c c c c c c} \hline  & \multicolumn{3}{c}{\(\mathbf{k=0}\)} & \multicolumn{3}{c}{\(\mathbf{k=1}\)} & \multicolumn{3}{c}{\(\mathbf{k=2}\)} \\ \hline \(i=1\) & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ \(i=2\) & 1 & 1 & 2 & 0 & 0 & 1 & 1 & 1 & 2 \\ \(i=3\) & 1 & 1 & 2 & 0 & 0 & 1 & 1 & 1 & 2 \\ \(i=4\) & 1 & 1 & 2 & 0 & 0 & 1 & 1 & 1 & 2 \\ \hline \end{tabular}
\end{table} 
Table 2: \(L(i,j,k)\) computed by recursive Formula (1). Let \(Z(i,j,k)\) denote the set of all LCSs of \(X[i:n]\) and \(Y[j:m]\) that exclude \(P\) as a substring of \(P[1:k]\oplus z\) for each \(z\in Z(i,j,k),1\leq i\leq n,1\leq j\leq m,0\leq k\leq r\). \(P[1:k]\) is an empty string if \(k=0\). The length of an LCS in \(Z(i,j,k)\) is denoted \(f(i,j,k)\). If we can compute \(f(i,j,k)\) for any \(1\leq i\leq n,1\leq j\leq m\) and \(0\leq k<r\) efficiently, then the length of an LCS of \(X\) and \(Y\) that excludes \(P\) as a substring must be \(f(1,1,0)\). We can obtain a recursive formula for computing \(f(i,j,k)\) with the following theorem. **Theorem 1**: _For the two input sequences, \(X=x_{1}x_{2}\cdots x_{n}\) and \(Y=y_{1}y_{2}\cdots y_{m}\), of lengths \(n\) and \(m\), respectively, and a constraint string, \(P=p_{1}p_{2}\cdots p_{r}\), of length \(r\), let \(Z(i,j,k)\) denote the set of all LCSs of \(X[i:n]\) and \(Y[j:m]\) that exclude \(P\) as a substring of \(P[1:k]\oplus z\) for each \(z\in Z(i,j,k)\)._  
_The length of an LCS in \(Z(i,j,k)\) is denoted, \(f(i,j,k)\)._  
_For any \(1\leq i\leq n,1\leq j\leq m\) and \(0\leq k<r\), \(f(i,j,k)\) can be computed with the following recursive Formula (2):_  
\[f(i,j,k)=\left\{ \begin{array}{ll}\max\left\{f(i+1,j+1,k),1+f(i+1,j+1,q) \right\}&\mbox{if $x_{i}=y_{j}$ and $q<r$}\\ \max\left\{f(i+1,j,k),f(i,j+1,k)\right\}&\mbox{otherwise}\end{array} \right. \tag{2}\]  
_where \(q=\sigma(P[1:k]\oplus x_{i})\), and the boundary conditions are \(f(i,m+1,k)=f(n+1,j,k)=0\) for any \(1\leq i\leq n,1\leq j\leq m\) and \(0\leq k\leq r\)._  
**Proof. ** For any \(1\leq i\leq n,1\leq j\leq m\) and \(0\leq k<r\), suppose \(f(i,j,k)=t\) and \(z=z_{1},\cdots,\)\(z_{t}\in Z(i,j,k)\). First, we note that for each pair, \((i^{\prime},j^{\prime}),1\leq i^{\prime}\leq n,1\leq j^{\prime}\leq m\), such that \(i^{\prime}\geq i\) and \(j^{\prime}\geq j\), we have \(f(i^{\prime},j^{\prime},k)\leq f(i,j,k)\), because a common subsequence, \(z\), of \(X[i^{\prime}:n]\) and \(Y[j^{\prime}:m]\) that excludes \(P\) as a substring of \(P[1:k]\oplus z\) is also a common subsequence of \(X[i:n]\) and \(Y[j:m]\) that excludes \(P\) as a substring of \(P[1:k]\oplus z\). (1) When \(x_{i}\
eq y_{j}\), we have \(x_{i}\
eq z_{1}\) or \(y_{j}\
eq z_{1}\). (1.1) If \(x_{i}\
eq z_{1}\), then \(z=z_{1},\cdots,z_{t}\) is a common subsequence of \(X[i+1:n]\) and \(Y[j:m]\) that excludes \(P\) as a substring of \(P[1:k]\oplus z\); thus, \(f(i+1,j,k)\geq t\).