2026/07/16 by Itai Boneh, Paweł Gawrychowski
#cs.DS
The LZ-End parsing of a length-n string is a variation of Lempel-Ziv compression introduced by Kreft and Navarro [DCC 2010], motivated by the lack of a linear-size structure with O(log n) access time for the classical variant. While the original paper was only able to provide efficient extraction from the phrase boundaries, recently Kempa and Saha [SODA 2022] established that, for a string S whose LZ-End parsing consists of z phrases, there exists a random access data structure that uses O(z) space and guarantees O(log4n ⋅ loglog n) query time. However, their proof does not yield an efficient construction algorithm, and their data structure is inherently randomized. We resolve both limitations by providing a deterministic, O(z)-space data structure that supports random access queries in polylogarithmic time and can be constructed in O(zlog2(n/z)) time directly from the LZ-End parsing. In addition to eliminating randomness and providing an efficient construction algorithm, the query time of our data structure is O(log2(n/z)), significantly improving upon the query time of Kempa and Saha. We also show that our techniques can be used to support the more general substring-extraction. Namely, we present a data structure with the same space and the same construction time that given two indices i and j, outputs S[i..j] in O(j-i+log2(n)/(z)) time.