Grammar-Compressed Indexes with Logarithmic Search Time

Francisco Claude, Gonzalo Navarro, Alejandro Pacheco

Let a text $T[\mathrm{1..}n]$ be the only string generated by a context-free grammar with $g$ (terminal and nonterminal) symbols, and of size $G$ (measured as the sum of the lengths of the…