A dynamic programming solution to a generalized LCS problem

• We point out that a previously proposed dynamic programming algorithm for the STR-EC-LCS problem cannot produce correct solution.
• We present a new dynamic programming solution for the STR-EC-LCS problem.
• The correctness of the new algorithm is proved.
• We investigate the efficient implementation of the algorithm.
• Our new algorithm may be a first correct dynamic programming algorithm for the STR-EC-LCS problem.

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 O(nmr)O(nmr).