Sublinear Space Algorithms for the Longest Common Substring Problem
From MaRDI portal
Publication:2921446
DOI10.1007/978-3-662-44777-2_50zbMath1425.68469arXiv1407.0522OpenAlexW1732081968MaRDI QIDQ2921446
Tomasz Kociumaka, Tatiana Starikovskaya, Hjalte Wedel Vildhøj
Publication date: 8 October 2014
Published in: Algorithms - ESA 2014 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.0522
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Related Items (10)
Approximating LZ77 via Small-Space Multiple-Pattern Matching ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Near-optimal quantum algorithms for string problems ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Dynamic and internal longest common substring ⋮ Longest Common Factor After One Edit Operation ⋮ Longest property-preserved common factor: a new string-processing framework ⋮ Longest common substring made fully dynamic ⋮ Longest common substrings with \(k\) mismatches ⋮ Linear-Time Algorithm for Long LCF with k Mismatches
This page was built for publication: Sublinear Space Algorithms for the Longest Common Substring Problem
