A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint (Q1736579)

Summary: 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 \textit{Y.-C. Chen} and \textit{K.-M. Chao} [J. Comb. Optim. 21, No. 3, 383--392 (2011; Zbl 1319.68263)], 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 \(O(nmr)\).