The substring inclusion constraint longest common subsequence problem can be solved in quadratic time

DOI10.1016/J.JDA.2012.11.004MaRDI QIDQ2376791zbMATH OpenOpenAlexFDO

Authors Muhammad Rashed Alam, M. Sohel Rahman

Publication date 24 June 2013

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2012.11.004

zbMATH Keywords

dynamic programminglongest common subsequence

Mathematics Subject Classification ID

Dynamic programming (90C39) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem.
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• Sublinear space algorithms for the longest common substring problem
• Linear time algorithms for generalizations of the longest common substring problem
• Longest common subsequence in sublinear space
• Time-space trade-offs for the longest common substring problem
• The constrained longest common subsequence problem
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint

Cites work

• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• New efficient algorithms for the LCS and constrained LCS problems
• 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

(2)

• Quadratic-time algorithm for a string constrained LCS problem
• String editing under pattern constraints

This page was built for publication: The substring inclusion constraint longest common subsequence problem can be solved in quadratic time

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