Skip to content

C++ source code for Lyndon Array algorithms: IDLA, BSLA, and TRLA

Notifications You must be signed in to change notification settings


Folders and files

Last commit message
Last commit date

Latest commit



9 Commits

Repository files navigation

Computing Lyndon Arrays

As part of of my Ph.D. research I worked on developing two algorithms (BSLA and TRLA) to compute Lyndon arrays. Herein, the C++ source code developed for the following algorithms: IDLA, BSLA, and TRLA. This code was used to take measurements and for empirical analysis. Details on these algorithms can be found on my personal website as they become available (and are published). This document and code has been updated since its initial release.


This algorithm, an iterative approach, is based on Duval’s work on Lyndon factorization. See lynarr.hpp.


This algorithm is based on the ideas of Baier’s Suffix Sort (Phase I); this implementation necessarily differs. See bsla.cpp.


This algorithm is based on Farach's approach on his linear algorithm for suffix tree construction. The first idea of this algorithm was proposed by Paracha, but, has since been improved. See trla.cpp and Tau.hpp.

Former Ph.D. Supervisors and Research Laboratory

Professor Frantisek (Franya) Franek, Ph.D., RNDr., L.E.L.
Professor Antoine Deza, Ph.D., P.Eng., Fields Institute Fellow
The Advanced Optimization Laboratory (AdvOL), McMaster University


The work, herein, is Copyright 2016--2020.
No rights are given to reproduce or modify this work.
If you are seeking rights to use some of the content within, please contact me via email (send to: michael [dot] liut [at]

Michael Liut, Ph.D., M.Eng., B.A.Sc.
Department of Mathematical and Computational Sciences
University of Toronto Mississauga
Mississauga, Ontario, Canada


C++ source code for Lyndon Array algorithms: IDLA, BSLA, and TRLA






No releases published