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

Let X1, X2, ..., Xs and Y1, Y2, ..., Yt be strings over an alphabet ∑, where s and t are positive integers. The longest common subsequence and substring problem for multiple strings X1, X2, ..., Xs and Y1, Y2, ..., Yt is to find the longest string which is a subsequence of X1, X2, ..., Xs and a substring of Y1, Y2, ..., Yt. In this paper, we propose an algorithm to solve the problem.