Prague Stringology Conference 2015

Shunsuke Inenaga

A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications

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.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation