A dynamic programming solution to a generalized LCS problem |
| |
Authors: | Lei Wang Xiaodong Wang Yingjie Wu Daxin Zhu |
| |
Affiliation: | 1. Microsoft AdCenter, Bellevue, WA 98004, USA;2. Faculty of Mathematics & Computer Science, Quanzhou Normal University, China;3. College of Mathematics & Computer Science, Fuzhou University, Fuzhou, China |
| |
Abstract: | In this paper, we consider a generalized longest common subsequence problem, the string-excluding constrained LCS problem. For the two input sequences X and Y of lengths n and m, and a constraint string P of length r, the problem is to find a common subsequence Z of X and Y excluding P as a substring and the length of Z is maximized. The problem and its solution were first proposed by Chen and Chao (2011) 1], 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. The correctness of the new algorithm is proved. The time complexity of the new algorithm is . |
| |
Keywords: | Design of algorithms Longest common subsequence Generalized LCS Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|