Skip to Main content Skip to Navigation
Journal articles

Fast parallel Lyndon factorization and applications

Abstract : It is shown that the Lyndon decomposition of a word of n symbols can be computed by an n-processors CRCW PRAM in O(log n) time. Extensions of the basic algorithm convey, within the same time and processors bounds, efficient parallel solutions to problems such as finding the lexicographically minimum or maximum suffix for all prefixes of the input string, and finding the lexicographically least rotation of all prefixes of the input.
Document type :
Journal articles
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, March 27, 2013 - 6:48:10 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Document(s) archivé(s) le : Friday, June 28, 2013 - 2:25:09 AM


Files produced by the author(s)


  • HAL Id : hal-00619181, version 1



Alberto Apostolico, Maxime Crochemore. Fast parallel Lyndon factorization and applications. Mathematical System Theory, 1995, 28 (2), pp.89-108. ⟨hal-00619181⟩