Skip to Main content Skip to Navigation
Conference papers

LPF computation revisited

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect 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


Files produced by the author(s)


  • HAL Id : hal-00741881, version 1


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⟩



Record views


Files downloads