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

Let $X_1,X_2,\mathrm{.}\mathrm{.}\mathrm{.},X_s$ and $Y_1,Y_2,\mathrm{.}\mathrm{.}\mathrm{.},Y_t$ be strings over an alphabet $\mathrm{\Sigma }$, where $s$ and $t$ are positive integers. The longest common subsequence and substring problem for multiple strings $X_1,X_2,\mathrm{.}\mathrm{.}\mathrm{.},X_s$ and $Y_1,Y_2,\mathrm{.}\mathrm{.}\mathrm{.},Y_t$ is to find the longest string which is a subsequence of $X_1,X_2,\mathrm{.}\mathrm{.}\mathrm{.},X_s$ and a substring of $Y_1,Y_2,\mathrm{.}\mathrm{.}\mathrm{.},Y_t$. In this paper, we propose an algorithm to solve the problem.