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

(21)

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

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)