Abstract : We present efficient algorithms for storing past segments of a text. They are computed using two previously computed read-only arrays (SUF and LCP) composing the Suffix Array of the text. They compute the maximal length of the previous factor (subword) occurring at each position of the text in a table called LPF. This notion is central both in many conservative text compression techniques and in the most efficient algorithms for detecting motifs and repetitions occurring in a text. The main results are: a linear-time algorithm that computes explicitly the permutation that transforms the LCP table into the LPF table; a time-space optimal computation of the LPF table; and an O(n log n) strong in-place computation of the LPF table.
https://hal-upec-upem.archives-ouvertes.fr/hal-00741881 Contributor : Maxime CrochemoreConnect in order to contact the contributor Submitted on : Wednesday, February 13, 2013 - 11:38:47 AM Last modification on : Saturday, January 15, 2022 - 3:57:44 AM Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:03 AM
Maxime Crochemore, Lucian Ilie, Costas S. Iliopoulos, Marcin Kubica, Wojciech Rytter, et al.. LPF computation revisited. IWOCA, 2009, Czech Republic. pp.158-169. ⟨hal-00741881⟩