Skip to Main content Skip to Navigation
Journal articles

Computing Longest Previous Factor in linear time and applications

Abstract : We give two optimal linear-time algorithms for computing the Longest Previous Factor (LPF) array corresponding to a string w. For any position i in w, LPF[i] gives the length of the longest factor of w starting at position i that occurs previously in w. Several properties and applications of LPF are investigated. They include computing the Lempel-Ziv factorization of a string and detecting all repetitions (runs) in a string in linear time independently of the integer alphabet size.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 6:43:53 PM
Last modification on : Saturday, January 15, 2022 - 3:58:04 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:00:10 AM


Files produced by the author(s)



Maxime Crochemore, Lucian Ilie. Computing Longest Previous Factor in linear time and applications. Information Processing Letters, Elsevier, 2008, 106 (2), pp.75-80. ⟨10.1016/j.ipl.2007.10.006⟩. ⟨hal-00619691⟩



Record views


Files downloads