  In this paper, we consider a generalized longest common subsequence problem
with multiple substring exclusion constrains. For the two input sequences $X$
and $Y$ of lengths $n$ and $m$, and a set of $d$ constrains $P=\{P_1,...,P_d\}$
of total length $r$, the problem is to find a common subsequence $Z$ of $X$ and
$Y$ excluding each of constrain string in $P$ as a substring and the length of
$Z$ is maximized. The problem was declared to be NP-hard\cite{1}, but we
finally found that this is not true. A new dynamic programming solution for
this problem is presented in this paper. The correctness of the new algorithm
is proved. The time complexity of our algorithm is $O(nmr)$.
