Fast parallel Lyndon factorization and applications

Alberto Apostolico (1, 2) , Maxime Crochemore (3)

1 Department of Computer Science [Purdue]
2 DISIM - Department of Information Engineering, Computer Science and Mathematics = Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica [L'Aquila]
3 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Mots clés: parallel computation; combinatorics on words; string matching; Lyndon words

Domaines: Algorithme et structure de données [cs.DS]

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