# Computing Maximal Lyndon Substrings of a String
## 1 Introduction
The execution and space characteristics are dominated by those of the first step, i.e., computation of the suffix array. We refer to this scheme as _SSLA_. In 2018, a linear algorithm to compute the Lyndon array from a given Burrows-Wheeler transform was presented [22]. Since the Burrows-Wheeler transform is computed in linear time from the suffix array, it is yet another scheme of how to obtain the Lyndon array via suffix sorting: compute the suffix array; from the suffix array, compute the Burrows-Wheeler transform, then compute the Lyndon array during the inversion of the Burrows-Wheeler transform. We refer to this scheme as _BWLA_. Figure 1: Algorithm _IDLA_. The introduction of [PERSON]'s suffix sort in 2015 and the consequent realization of the connection to right-maximal Lyndon substrings brought up the realization that there was an elementary (not relying on a pre-processed global data structure such as a suffix array or a Burrows-Wheeler transform) algorithm to compute the Lyndon array, and that, despite its original clumsiness, could be eventually refined to outperform any _SSLA_ or _BWLA_ implementation: any implementation of a suffix sorting-based scheme requires a full suffix sort and then some additional processing, while [PERSON]'s approach is \"just\" a partial suffix sort; see [23]. In this work, we present two additional algorithms for the Lyndon array not discussed in [19]. The C++ source code of the three implementations _IDLA_, _TRLA_, and _BSLA_ is available; see [24]. Note that the procedure _IDLA_ is in the lynarr.hpp file. The first algorithm presented here is _TRLA_. _TRLA_ is a \(\tau\)-reduction based Lyndon array algorithm that follows [PERSON]'s approach used in his remarkable linear algorithm for suffix tree construction [25] and reproduced very successfully in all linear algorithms for suffix sorting (e.g., see [26; 21] and the references therein). [PERSON]'s approach follows the Cooley-Tukey algorithm for the fast Fourier transform relying on recursion to lower the quadratic complexity to \(O(n\;\log(n))\) complexity; see [27]. _TRLA_ was first introduced by the authors in 2019 (see [28; 29]) and presented as a part of [PERSON]'s Ph.D. thesis [30]. The second algorithm, _BSLA_, is a [PERSON]'s sort-based Lyndon array algorithm. _BSLA_ is based on the idea of Phase I of [PERSON]'s suffix sort, though our implementation necessarily differs from [PERSON]'s. _BSLA_ was first introduced at the Prague Stringology Conference 2018 [23] and also presented as a part of [PERSON]'s Ph.D. thesis [30] in 2019; here, we present a complete and refined theoretical analysis of the algorithm and a more efficient implementation than that initially introduced. The paper is structured as follows: In Section 2, the basic notions and terminology are presented. In Section 3, the _TRLA_ algorithm is presented and analysed. In Section 4, the _BSLA_ algorithm is presented and analysed. In Section 5, the datasets with random strings of various lengths and over various alphabets and other datasets used in the empirical tests are described. In Section 6, the conclusion of the research and the future work are presented. The results of the empirical measurements of the performance of _IDLA_, _TRLA_, and _BSLA_ on those datasets are presented in Section 7 in both tabular and graphical forms.