A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
type: Item
instance of: scholarly article
title: A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
zbMATH Open document ID: 1461.68273
author: Daxin Zhu
author: Xiaodong Wang
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 7042174
zbMATH Keywords: constrained LCS
zbMATH Keywords: string-excluding
zbMATH Keywords: dynamic programming
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6030485
OpenAlex ID: W2052437266
cites work: The constrained longest common subsequence problem
cites work: Q2970219
cites work: A new efficient algorithm for computing the longest common subsequence
cites work: AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS
cites work: On the generalized constrained longest common subsequence problems
cites work: Fast Pattern Matching in Strings
cites work: Quadratic-time algorithm for a string constrained LCS problem
cites work: Efficient algorithms for the longest common subsequence problem with sequential substring constraints
DOI: 10.3390/A6030485
description: scientific article; zbMATH DE number 7042174