  Recently, Conte et al. generalized the longest-common prefix (LCP) array from
strings to Wheeler DFAs, and they showed that it can be used to efficiently
determine matching statistics on a Wheeler DFA [DCC 2023]. However, storing the
LCP array requires $ O(n \log n) $ bits, $ n $ being the number of states,
while the compact representation of Wheeler DFAs often requires much less
space. In particular, the BOSS representation of a de Bruijn graph only
requires a linear number of bits, if the size of alphabet is constant.
  In this paper, we propose a sampling technique that allows to access an entry
of the LCP array in logarithmic time by only storing a linear number of bits.
We use our technique to provide a space-time trade-off to compute matching
statistics on a Wheeler DFA. In addition, we show that by augmenting the BOSS
representation of a $ k $-th order de Bruijn graph with a linear number of bits
we can navigate the underlying variable-order de Bruijn graph in time
logarithmic in $ k $, thus improving a previous bound by Boucher et al. which
was linear in $ k $ [DCC 2015].

Data Structures and Algorithms