|
In this talk, we introduce our recent data structure for
longest common extension (LCE) queries on grammar-compressed strings.
Our preprocessing input is a straight-line program (SLP) of size n
describing a string w of length N,
which is essentially a CFG in the Chomsky normal form generating only w.
We can preprocess the input SLP in
O(n log log n log N log*N)
time
so that later, given two variables and two positions in the strings derived by the variables,
we can answer the corresponding LCE query in
O(log N log*N)
time.
Our LCE data structure requires
O(z log N log*N)
words of space, where z is the size of the Lempel-Ziv 77 factorization of
w.
We also show several applications of our LCE data structure on SLPs.
|
