In-Place Longest Common Extensions.
Nicola Prezza · arXiv (Cornell University) · 2016
Longest Common Extension (LCE) queries are a fundamental sub-routine in several string-processing algorithms, including (but not limited to) suffix-sorting, string matching, compression, and identification of repeats and palindrome factors. A LCE query takes as input two positions $i,j$ in a text $T\in\Sigma^n$ and returns the length $\ell$ of the longest common prefix between $T$'s $i$-th and $j$-th suffixes. In this paper, we present the following result: we can replace the (plain) text with a data structure of the \emph{exact same size}---$n\lceil\log_2|\Sigma|\rceil$ bits---supporting text extraction in optimal time and LCE queries in logarithmic time---i.e. \emph{exponentially} faster than what can be achieved using the plain text alone. Our structure can be built in $\mathcal O(n\log n)$ expected time and linear space. We show that our result is a powerful tool that can be used to efficiently solve in-place a wide variety of string processing problems: we provide the first in-place algorithms to compute the LCP array in $\mathcal O(n\log n)$ expected time (the previous fastest in-place algorithm runs in $\mathcal O(n^2)$ time) and to suffix-sort---with high probability of success---any set of $b$ text suffixes in $\mathcal O(n+b\log^2 n)$ expected time (the previous fastest in-place algorithm runs in $\mathcal O(nb)$ time).