We consider the problem of computing online the Longest Previous Factor array LPF[1, n] of a text T of length n. For each, 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. 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 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 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.
|Data di pubblicazione:||2020|
|Titolo:||Faster Online Computation of the Succinct Longest Previous Factor Array|
|Titolo del libro:||Beyond the Horizon of Computability: 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy, June 29–July 3, 2020, Proceedings|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/978-3-030-51466-2_31|
|Appare nelle tipologie:||4.1 Articolo in Atti di convegno|
File in questo prodotto: