Time-space trade-offs for the longest common substring problem

DOI10.1007/978-3-642-38905-4_22MaRDI QIDQ4928575zbMATH OpenOpenAlexFDO

Authors Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38905-4_22

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Sublinear space algorithms for the longest common substring problem
• Time-Space Trade-Offs for Longest Common Extensions
• Time-space trade-offs for longest common extensions
• Longest common extensions in sublinear space
• Linear time algorithms for generalizations of the longest common substring problem

Cited in

(16)

• Linear time algorithms for generalizations of the longest common substring problem
• Longest common substring made fully dynamic
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• A substring-substring LCS data structure
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Time-Space Trade-Offs for Longest Common Extensions
• Linear-time algorithm for long LCF with \(k\) mismatches
• Longest common factor after one edit operation
• Longest common substring with approximately \(k\) mismatches
• Dynamic and internal longest common substring
• Longest property-preserved common factor: a new string-processing framework
• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• Near-optimal quantum algorithms for string problems
• Sublinear space algorithms for the longest common substring problem
• Longest common substrings with \(k\) mismatches
• Longest common subsequence in sublinear space

This page was built for publication: Time-space trade-offs for the longest common substring problem

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