A dynamic programming solution to a generalized LCS problem

DOI10.1016/J.IPL.2013.07.005MaRDI QIDQ2445236zbMATH OpenOpenAlexFDO

Authors Lei Wang, Yingjie Wu, Daxin Zhu, Xiaodong Wang

Publication date 14 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.7183

zbMATH Keywords

design of algorithmsdynamic programminggeneralized LCSlongest common subsequence

Mathematics Subject Classification ID

Algorithms on strings (68W32) Dynamic programming (90C39)

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 Chaocite{1}, but we found that their algorithm can not 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)$.

Recommendations

• A faster algorithm for solving general LPs
• Generalizations and applications of a class of dynamic programming problems
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• scientific article; zbMATH DE number 4083396
• A linear space algorithm for the LCS problem
• scientific article; zbMATH DE number 1406022
• New efficient algorithms for the LCS and constrained LCS problems
• New algorithms for the LCS problem
• A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
• Generalization of the dynamic programming scheme

Cites work

• A new efficient algorithm for computing the longest common subsequence
• A simple algorithm for the constrained sequence problems
• An algorithm and applications to sequence alignment with weighted constraints
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 6697960 (Why is no real title available?)
• Introduction to algorithms.
• On the generalized constrained longest common subsequence problems
• Quadratic-time algorithm for a string constrained LCS problem
• The constrained longest common subsequence problem

Cited in

(11)

• A linear space algorithm for the LCS problem
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
• Generalized LCS
• Solving RCPSP/max by lazy clause generation
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• Faster STR-EC-LCS computation
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• scientific article; zbMATH DE number 1406022 (Why is no real title available?)
• The generalized constrained longest common subsequence in the run-length encoded format
• Efficient algorithms for enumerating maximal common subsequences of two strings

This page was built for publication: A dynamic programming solution to a generalized LCS problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445236)