Computing the Longest Previous Factor

Maxime Crochemore (1) , Lucian Ilie , Costas S. Iliopoulos (2) , Marcin Kubica (1) , Wojciech Rytter (3) , Tomasz Walen

1 inconnu temporaire UPEMLV
2 King‘s College London
3 Institute of Informatics [Warsaw]

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.

Mots clés: longest previous factor; suffix array; longest common prefix; Ziv-Lempel factorization; text compression; string repetitions

Domaines: Algorithme et structure de données [cs.DS]

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