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.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2013, 34 (1), pp.15 - 26. 〈10.1016/j.ejc.2012.07.011〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01616480
Contributeur : Maxime Crochemore <>
Soumis le : vendredi 13 octobre 2017 - 16:52:00
Dernière modification le : vendredi 20 avril 2018 - 08:58:44

Fichier

LPF-revisited.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

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〉

Partager

Métriques

Consultations de la notice

125

Téléchargements de fichiers

50