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.
https://hal-upec-upem.archives-ouvertes.fr/hal-01616480 Contributor : Maxime CrochemoreConnect in order to contact the contributor Submitted on : Friday, October 13, 2017 - 4:52:00 PM Last modification on : Saturday, January 15, 2022 - 3:58:12 AM
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⟩