Sublinear space algorithms for the longest common substring problem

DOI10.1007/978-3-662-44777-2_50MaRDI QIDQ2921446zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Abstract: Given $m$ documents of total length $n$, we consider the problem of finding a longest string common to at least $dgeq2$ of the documents. This problem is known as the emph{longest common substring (LCS) problem} and has a classic $O(n)$ space and $O(n)$ time solution (Weiner [FOCS'73], Hui [CPM'92]). However, the use of linear space is impractical in many applications. In this paper we show that for any trade-off parameter $1leqauleqn$, the LCS problem can be solved in $O(au)$ space and $O(n^2/au)$ time, thus providing the first smooth deterministic time-space trade-off from constant to linear space. The result uses a new and very simple algorithm, which computes a $au$-additive approximation to the LCS in $O(n^2/au)$ time and $O(1)$ space. We also show a time-space trade-off lower bound for deterministic branching programs, which implies that any deterministic RAM algorithm solving the LCS problem on documents from a sufficiently large alphabet in $O(au)$ space must use $Omega(nsqrtlog(n/(aulogn))/loglog(n/(aulogn))$ time.

Recommendations

• Time-space trade-offs for the longest common substring problem
• Longest common subsequence in sublinear space
• Longest common extensions in sublinear space
• Time-space trade-offs for longest common extensions
• Time-Space Trade-Offs for Longest Common Extensions

Cited in

(25)

• Longest common substring made fully dynamic
• Sparse LCS Common Substring Alignment
• Substring complexity in sublinear space
• A substring-substring LCS data structure
• Linear-time algorithm for long LCF with k mismatches
• Sparse LCS common substring alignment
• Time-space trade-offs for the longest common substring problem
• Longest common factor after one edit operation
• Longest common substring with approximately \(k\) mismatches
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings
• Dynamic and internal longest common substring
• Longest property-preserved common factor: a new string-processing framework
• Dynamic longest common substring in polylogarithmic time
• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• Near-optimal quantum algorithms for string problems
• LP-based heuristics for the distinguishing string and substring selection problems
• A linear-space algorithm for the substring constrained alignment problem
• Internal pattern matching in small space and applications
• Longest common substrings with k mismatches
• On the common substring alignment problem
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• The longest common substring problem
• Longest common subsequence in sublinear space
• A simple grammar-based index for finding approximately longest common substrings

This page was built for publication: Sublinear space algorithms 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 Q2921446)