Affordable Access

Longest Common Extensions in Sublinear Space

Authors
  • Bille, Philip
  • Gørtz, Inge Li
  • Knudsen, Mathias Bæk Tejs
  • Lewenstein, Moshe
  • Vildhøj, Hjalte Wedel
Type
Preprint
Publication Date
Apr 10, 2015
Submission Date
Apr 10, 2015
Identifiers
arXiv ID: 1504.02671
Source
arXiv
License
Yellow
External links

Abstract

The longest common extension problem (LCE problem) is to construct a data structure for an input string $T$ of length $n$ that supports LCE$(i,j)$ queries. Such a query returns the length of the longest common prefix of the suffixes starting at positions $i$ and $j$ in $T$. This classic problem has a well-known solution that uses $O(n)$ space and $O(1)$ query time. In this paper we show that for any trade-off parameter $1 \leq \tau \leq n$, the problem can be solved in $O(\frac{n}{\tau})$ space and $O(\tau)$ query time. This significantly improves the previously best known time-space trade-offs, and almost matches the best known time-space product lower bound.

Report this publication

Statistics

Seen <100 times