A Simple Algorithm for the Constrained Sequence Problems

Abstract

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.

https://doi.org/10.1016/j.ipl.2004.02.008

Cited by in corpus (2)

• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Faster STR-EC-LCS Computation