A Simple Algorithm for Solving for the Generalized Longest Common Subsequence (LCS) Problem with a Substring Exclusion Constraint

Algorithms

Daxin Zhu¹ 

[1] Faculty of Mathematics & Computer Science, Quanzhou Normal University, Quanzhou 362000, China; E-Mail:

关键词: constrained LCS;    string-excluding;    dynamic programming;   

DOI  :  10.3390/a6030485

来源: mdpi

【 摘 要 】

This paper studies the string-excluding (STR-EC)-constrained longest common subsequence (LCS) problem, a generalized LCS problem. For the two input sequences, X and Y, of lengths n and m and a constraint string, P, of length r, the goal is to find the longest common subsequence, Z, of X and Y that excludes P as a substring. The problem and its solution were first proposed by Chen and Chao, but we found that their algorithm cannot solve the problem correctly. A new dynamic programming solution for the STR-EC-LCS problem is then presented in this paper, and the correctness of the new algorithm is proven. The time complexity of the new algorithm is .

【 授权许可】

CC BY   
© 2013 by the authors; licensee MDPI, Basel, Switzerland.