# Computing Maximal Lyndon Substrings of a String
## 1 Introduction  
In _combinatorics on words_, Lyndon words play a very important role. _Lyndon words_, a special case of Hall words, were named after [PERSON], who was looking for a suitable description of the generators of free Lie algebras [1]. Despite their humble beginnings, to date, Lyndon words have facilitated many applications in mathematics and computer science, some of which are: constructing de Bruijn sequences, constructing bases in free Lie algebras, finding the lexicographically smallest or largest substring in a string, and succinct prefix matching of highly periodic strings; see [PERSON] et al. [2], and the informative paper by [PERSON] and [PERSON] [3] and the references therein. The pioneering work on Lyndon decomposition was already introduced by [PERSON], [PERSON], and [PERSON] in [4]. The _Lyndon decomposition theorem_ is not explicitly stated there; nevertheless, it follows from the work presented there. **Theorem 1** (Lyndon decomposition theorem, [PERSON], 1958). : _For any word \(\mathbf{x}\), there are unique Lyndon words \(\mathbf{u}_{1},...,\mathbf{u}_{k}\) so that \(\mathbf{u}_{i+1}\prec\mathbf{u}_{i}\) for any \(1\leq i<k\), and \(\mathbf{x}=\mathbf{u}_{1}\mathbf{u}_{2}\ldots\mathbf{u}_{k}\), where \(\prec\) denotes the lexicographic ordering._  
As there exists a bijection between Lyndon words over an alphabet of cardinality \(k\) and irreducible polynomials over \(\mathbf{F}_{k}\)[5], many results are known about this factorization: the average number of factors, the average length of the longest factor [6] and of the shortest [7]. Several algorithms deal with Lyndon factorization. [PERSON] gave in [8] an elegant algorithm that computes, in linear time and in-place, the factorization of a word into Lyndon words. More about its implementation can be found in [9]. In [10], [PERSON] and [PERSON] presented an algorithm generating all Lyndon words up to a given length in lexicographical order. This algorithm runs in a constant average time. Two of the latest applications of Lyndon words are due to [PERSON] et al. In [11], they employed Lyndon roots of runs to prove the runs conjecture that _the number of runs in a string is bounded by the length of the string_. In the same paper, they presented an algorithm to compute all the runs in a string in linear time that requires the knowledge of all right-maximal Lyndon substrings of the input string with respect to an order of the alphabet and its inverse. The latter result was the major reason for our interest in computing the right-maximal Lyndon substrings of a given string. Though the terms _word_ and _string_ are interchangeable, and so are the terms _subword_ and _substring_, in the following, we prefer to use exclusively the terms _string_ and _substring_ to avoid confusing the reader. There are at least two reasons for having an efficient algorithm for identifying all right-maximal Lyndon substrings of a string: firstly, [PERSON] et al. published in 2017 [11] a linear algorithm to compute all runs in a string that depends on knowing all right-maximal Lyndon substrings of the input string, and secondly, in 2017, [PERSON] et al. in [12] showed a linear equivalence of sorting suffixes and sorting right-maximal Lyndon substrings, inspired by Phase II of a suffix sorting algorithm introduced by [PERSON] in 2015 (Master's thesis [13]) and published in 2016 [14]. The most significant feature of the runs algorithm presented in [11] is that it relies on knowing the right-maximal Lyndon substrings of the input string for some order of the alphabet and for the inverse of that order, while all other linear algorithms for runs rely on Lempel-Ziv factorization of the input string. It also raised the issue about which approach may be more efficient: to compute the Lempel-Ziv factorization or to compute all right-maximal Lyndon substrings. There are several efficient linear algorithms for Lempel-Ziv factorization (e.g., see [15; 16] and the references therein).