Computing the Longest Previous Factor

Abstract : The Longest Previous Factor array gives, for each position i in a string y, the length of the longest factor (substring) of y that occurs both at i and to the left of i in y. The Longest Previous Factor array is central in many text compression techniques as well as in the most efficient algorithms for detecting motifs and repetitions occurring in a text. Computing the Longest Previous Factor array requires usually the Suffix Array and the Longest Common Prefix array. We give the first time–space optimal algorithm that computes the Longest Previous Factor array, given the Suffix Array and the Longest Common Prefix array. We also give the first linear-time algorithm that computes the permutation that applied to the Longest Common Prefix array produces the Longest Previous Factor array.
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01616480
Contributor : Maxime Crochemore <>
Submitted on : Friday, October 13, 2017 - 4:52:00 PM
Last modification on : Friday, April 20, 2018 - 8:58:44 AM

File

LPF-revisited.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Maxime Crochemore, Lucian Ilie, Costas Iliopoulos, Marcin Kubica, Wojciech Rytter, et al.. Computing the Longest Previous Factor. European Journal of Combinatorics, Elsevier, 2013, 34 (1), pp.15 - 26. ⟨10.1016/j.ejc.2012.07.011⟩. ⟨hal-01616480⟩

Share

Metrics

Record views

174

Files downloads

169