 |
HAL UPEC - UPEM Portal |  |
 |
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.
Cited literature [13 references]
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 : Monday, October 19, 2020 - 8:26:02 PM
Long-term archiving on: : Friday, June 28, 2013 - 2:25:09 AM
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, March 27, 2013 - 6:48:10 AM
Last modification on : Monday, October 19, 2020 - 8:26:02 PM
Long-term archiving on: : Friday, June 28, 2013 - 2:25:09 AM
File
Fast_Parallel_Lyndon_Factoriza...
Files produced by the author(s)