An Algorithm for the Constrained Longest Common Subsequence and Substring Problem

Let $\mathrm{\Sigma }$ be an alphabet. For two strings $X$, $Y$, and a constrained string $P$ over the alphabet $\mathrm{\Sigma }$, the constrained longest common subsequence and substring problem for two strings $X$ and $Y$ with respect to $P$ is to find a longest string $Z$ which is a subsequence of $X$, a substring of $Y$, and has $P$ as a subsequence. In this paper, we propose an algorithm for the constrained longest common subsequence and substring problem for two strings with a constrained string.