Computing the Longest Previous Factor

Maxime Crochemore (1) , Lucian Ilie (2) , Costas Iliopoulos (1) , Marcin Kubica (3) , Wojciech Rytter (3) , Tomasz Waleń

1 Informatics
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
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 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.

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

Maxime Crochemore, Lucian Ilie, Costas Iliopoulos, Marcin Kubica, Wojciech Rytter, et al.. Computing the Longest Previous Factor. European Journal of Combinatorics, 2013, 34 (1), pp.15 - 26. ⟨10.1016/j.ejc.2012.07.011⟩. ⟨hal-01616480⟩