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 metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00741881
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 11:38:47 AM
Last modification on : Monday, June 8, 2020 - 10:54:02 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:03 AM

File

LPF_computation_revisited.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00741881, version 1

Citation

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⟩

Share

Metrics

Record views

267

Files downloads

276