An Efficient Dynamic Programming Algorithm for SEQ-IC-SEQ-EC-LCS Problem

In this paper, we consider a generalized longest common subsequence problem, in which a constraining sequence of length s must be included as a subsequence and the other constraining sequence of length t must be excluded as a subsequence of two main sequences and the length of the result must be maximal. For the two input sequences X and Y of lengths n and m, and the given two constraining sequences of length s and t, we present an O(nmst) time dynamic programming algorithm for solving the new generalized longest common subsequence problem. The correctness of the new algorithm is demonstrated.