Efficient Computation of Longest Common Subsequences with Multiple Substring Inclusive Constraints

Abstract

Abstract

In this article, we consider a generalized longest common subsequence (LCS) problem with multiple substring inclusive constraints. For the two input sequences X and Y of lengths n and m, and a set of d constraints of total length r, the problem is to find a common subsequence Z of X and Y including each of constraint string in P as a substring and the length of Z is maximized. A new dynamic programming solution to this problem is presented in this article. The correctness of the new algorithm is proved. The time complexity of our algorithm is . In the case of the number of constraint strings is fixed, our new algorithm for the generalized LCS problem with multiple substring inclusive constraints requires \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\textbf{\textit{O ( nmr )}}$$ \end{document} time and space.