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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619691
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 6:43:53 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:00:10 AM

File

IPL07.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

406

Files downloads

1022