Quadratic-time algorithm for a string constrained LCS problem

DOI10.1016/J.IPL.2012.02.007MaRDI QIDQ436553zbMATH OpenOpenAlexFDO

Authors Sebastian Deorowicz

Publication date 25 July 2012

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

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

zbMATH Keywords

longest common subsequencesequence similarityconstrained longest common subsequence

Mathematics Subject Classification ID

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

Abstract: The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster.

Recommendations

• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• The constrained longest common subsequence problem
• New efficient algorithms for the LCS and constrained LCS problems
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

Cites work

• A faster algorithm computing string edit distances
• Algorithms on Strings, Trees and Sequences
• Bit-parallel algorithm for the constrained longest common subsequence problem
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Directed acyclic subsequence graph -- overview
• On the generalized constrained longest common subsequence problems
• Searching subsequences
• The constrained longest common subsequence problem

Cited in

(14)

• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• Faster STR-IC-LCS computation via RLE
• Computing longest common square subsequences
• Maximal common subsequence algorithms
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Faster space-efficient STR-IC-LCS computation
• String editing under pattern constraints
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• A dynamic programming solution to a generalized LCS problem
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Space-efficient STR-IC-LCS computation
• Approximating LCS in Linear Time: Beating the √n Barrier
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• Faster STR-EC-LCS computation

This page was built for publication: Quadratic-time algorithm for a string constrained LCS problem

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