An Algorithm for the Constrained Longest Common Subsequence and Substring Problem for Multiple Strings*

Let ∑ be an alphabet. For multiple strings X, Y1, Y2, ..., Yn, and a constrained string P over the alphabet ∑, we introduce the constrained longest common subsequence and substring problem for strings X, Y1, Y2, ..., Yn with respect to P as to find a longest string Z which is a subsequence of X, a substring of Y1, Y2, ..., and Yn, and has P as a subsequence. In this paper, we propose an algorithm for solving the above problem.