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.
dynamic programming generalized lcs design of algorithms longest common subsequence