Faster Online Computation of the Succinct Longest Previous Factor Array

We consider the problem of computing online the Longest Previous Factor array LPF[1, n] of a text T of length n. For each [Formula: see text], LPF[i] stores the length of the longest factor of T with at least two occurrences, one ending at i and the other at a previous position [Formula: see text]. We present an improvement over the previous solution by Okanohara and Sadakane (ESA 2008): our solution uses less space (compressed instead of succinct) and runs in [Formula: see text] time, thus being faster by a logarithmic factor. As a by-product, we also obtain the first online algorithm computing the Longest Common Suffix (LCS) array (that is, the LCP array of the reversed text) in [Formula: see text] time and compressed space. We also observe that the LPF array can be represented succinctly in 2n bits. Our online algorithm computes directly the succinct LPF and LCS arrays.