An Algorithm for the Constrained Longest Common Subsequence and Substring Problem

Abstract

Let $\hat{I}\pounds$ be an alphabet. For two strings $X$, $Y$, and a constrained string $P$ over the alphabet $\hat{I}\pounds$, 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.

arXiv admin note: text overlap with arXiv:2308.00925