Tight Lower Bounds for the Longest Common Extension Problem

Abstract

The longest common extension problem is to preprocess a given string of length $n$ into a data structure that uses $S(n)$ bits on top of the input and answers in $T(n)$ time the queries $LCE(i,j)$ computing the length of the longest string that occurs at both positions $i$ and $j$ in the input. We prove that the trade-off $S(n)T(n)=\Omega (n\log n)$ holds in the non-uniform cell-probe model provided that the input string is read-only, each letter occupies a separate memory cell, $S(n)=\Omega (n)$, and the size of the input alphabet is at least $2^{8\lceil S(n)/n\rceil }$. It is known that this trade-off is tight.

5 pages, accepted to Information Processing Letters

References in corpus (3)

• Geometry of quantum states: new construction of positive maps
• Longest Common Extensions with Recompression
• Fast Longest Common Extensions in Small Space