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 arrays. 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 [22 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01806294
Contributor : Maxime Crochemore <>
Submitted on : Friday, June 1, 2018 - 7:03:53 PM
Last modification on : Wednesday, June 6, 2018 - 10:25:56 AM
Long-term archiving on : Sunday, September 2, 2018 - 3:58:50 PM

File

ComputingLPF.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01806294, version 1

Collections

Citation

Maxime Crochemore, Lucian Ilie, Costas Iliopoulos, Marcin Kubica, Wojciech Rytter, et al.. Computing the Longest Previous Factor. European Journal of Combinatorics, Elsevier, 2013. ⟨hal-01806294⟩

Share

Metrics

Record views

27

Files downloads

84