An Algorithm for the Longest Common Subsequence and Substring Problem

In this note, we first introduce a new problem called the longest common subsequence and substring problem. Let X and Y be two strings over an alphabet ∑. The longest common subsequence and substring problem for X and Y is to find the longest string, which is a subsequence of X and a substring of Y. We propose an algorithm to solve the problem.