The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
From MaRDI portal
Publication:2376791
DOI10.1016/J.JDA.2012.11.004zbMATH Open1267.68319OpenAlexW2093750732MaRDI QIDQ2376791FDOQ2376791
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
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
- The constrained longest common subsequence problem
- On the generalized constrained longest common subsequence problems
- 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
- Quadratic-time algorithm for a string constrained LCS problem
Cited In (2)
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)
