In this paper we address the constrained longest common subsequence problem. Given two sequences $X$, $Y$ and a constrained sequence $P$, a sequence $Z$ is a constrained longest common subsequence for $X$ and $Y$ with respect to $P$ if $Z$ is the longest subsequence of $X$ and $Y$ such that $P$ is a subsequence of $Z$. Recently, Tsai \cite{Tsai} proposed an $O(n^2 \cdot m^2 \cdot r)$ time algorithm to solve this problem using dynamic programming technique, where $n$, $m$ and $r$ are the lengths of $X$, $Y$ and $P$, respectively. In this paper, we present a simple algorithm to solve the constrained longest common subsequence problem in $O(n \cdot m \cdot r)$ time and show that the constrained longest common subsequence problem is equivalent to a special case of the constrained multiple sequence alignment problem which can also be solved.
翻译:在本文中,我们处理受限制的最长共同后继问题。考虑到两个序列,即X美元、Y美元和受限制的后继问题,如果Z美元是X美元和Y美元这两个最长后继问题,那么,Z美元是受限制的最长共同后继问题。最近,Tsai\cite{Tsai}提议用一个美元(n_2\cdot m%2\cdot r) 时间算法,用动态程序技术解决这个问题,其中美元、美元和美元分别为X美元、美元和美元。在本文件中,我们提出了一个简单的算法,以解决美元(n\cdot m\cdotr)中受限制后继问题,并表明受限制后继问题相当于一个特殊情况,即限制的多个序列调整问题也能够得到解决。