Quadratic-time algorithm for a string constrained LCS problem

DOI10.1016/J.IPL.2012.02.007zbMath1243.68333arXiv1106.6342OpenAlexW2085086876MaRDI QIDQ436553

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)

Related Items (10)

The substring inclusion constraint longest common subsequence problem can be solved in quadratic time ⋮ A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ Space-efficient STR-IC-LCS computation ⋮ A dynamic programming solution to a generalized LCS problem ⋮ 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 ⋮ A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint ⋮ Unnamed Item ⋮ Maximal common subsequence algorithms

Cites Work

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

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