 |
HAL UPEC - UPEM Portal |  |
 |
Journal articles
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.
Cited literature [21 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-01616480
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Friday, October 13, 2017 - 4:52:00 PM
Last modification on : Tuesday, October 19, 2021 - 11:26:22 AM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Friday, October 13, 2017 - 4:52:00 PM
Last modification on : Tuesday, October 19, 2021 - 11:26:22 AM
File
LPF-revisited.pdf
Publisher files allowed on an open archive