Longest Common Extensions in Sublinear Space

2015/04/10 by Bille, Philip, Gørtz, Inge Li, Knudsen, Mathias Bæk Tejs +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1504.02671

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 ≤ τ≤ n, the problem can be solved in O(\fracnτ) space and O(τ) query time. This significantly improves the previously best known time-space trade-offs, and almost matches the best known time-space product lower bound.

Related

• Time-Space Trade-Offs for Longest Common Extensions
• Deterministic sub-linear space LCE data structures with efficient construction
• Fast Longest Common Extensions in Small Space
• Tight Lower Bounds for the Longest Common Extension Problem
• Longest Common Extensions with Recompression