An Efficient Algorithm for a New Constrained LCS Problem

摘要

The solution to a generalized longest common subsequence problem is addressed in this paper. In this problem, two given sequences of their length s and t must be included as the subsequences of the two main sequences A and B, and the result subsequences must be the longest. If the lengths of the two main sequences A and B are n and m, and the lengths of their two constrained sequences are s and t respectively, the time complexity of the dynamic programming algorithm presented in this paper to solve the new generalized LCS problem must be O(nmst).