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

https://hal-upec-upem.archives-ouvertes.fr/hal-00619181
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, March 27, 2013 - 6:48:10 AM
Last modification on : Tuesday, July 30, 2019 - 10:35:10 AM
Long-term archiving on: Friday, June 28, 2013 - 2:25:09 AM

File

Fast_Parallel_Lyndon_Factoriza...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619181, version 1

Collections

Citation

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

Share

Metrics

Record views

232

Files downloads

95