Skip to Main content Skip to Navigation
Conference papers

A simple algorithm for computing the Lempel-Ziv factorization

Abstract : We give a space-efficient simple algorithm for computing the Lempel-Ziv factorization of a string. For a string of length n over an integer alphabet, it runs in O(n) time independently of alphabet size and uses o(n) additional space.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620138
Contributor : Maxime Crochemore <>
Submitted on : Thursday, February 14, 2013 - 8:40:27 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Wednesday, May 15, 2013 - 2:35:08 AM

File

KMP.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620138, version 1

Citation

Maxime Crochemore, Lucian Ilie, William F. Smyth. A simple algorithm for computing the Lempel-Ziv factorization. 18th Data Compression Conference (DCC'08), 2008, United States. pp.482-488. ⟨hal-00620138⟩

Share

Metrics

Record views

333

Files downloads

495