Conference paper
Sublinear Space Algorithms for the Longest Common Substring Problem
Given m documents of total length n, we consider the problem of finding a longest string common to at least d ≥ 2 of the documents. This problem is known as the 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 1 ≤ τ ≤ n, the LCS problem can be solved in O(τ) space and O(n2/τ) 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 τ-additive approximation to the LCS in O(n2/τ) 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(τ) space must use Ω(n√log(n/(τ log n))/log log(n/(τ log n)) time.
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2014 |
Pages: | 605-617 |
Proceedings: | 22nd Annual European Symposium on Algorithms 2014European Symposium on Algorithms |
Series: | Lecture Notes in Computer Science |
Journal subtitle: | Proceedings of the 22th Annual European Symposium 2014 |
ISBN: | 3662447762 , 3662447770 , 9783662447765 and 9783662447772 |
ISSN: | 03029743 |
Types: | Conference paper |
DOI: | 10.1007/978-3-662-44777-2_50 |