# Computing Maximal Lyndon Substrings of a String
## 1 Introduction
Interestingly, [PERSON] [17] showed that for a general alphabet, in the decision tree model, the runs problem is easier than the Lempel-Ziv decomposition. His result supports the conjecture that there must be a linear random access memory model algorithm finding all runs. [PERSON] introduced in [13], and published in [14], a new algorithm for suffix sorting. Though Lyndon strings were never mentioned in [13; 14], it was noticed by [PERSON] in a personal communication [18] that Phase I of [PERSON]'s suffix sort identifies and sorts all right-maximal Lyndon substrings. The right-maximal Lyndon substrings of a string \(\mathbf{x}=\mathbf{x}[1..n]\) can be best encoded in the so-called _Lyndon array_, introduced in [19] and closely related to the _Lyndon tree_ of [20]: an integer array \(\mathcal{L}[1..n]\) so that for any \(i\in 1..n\), \(\mathcal{L}[i]=\)_the length of the right-maximal Lyndon substring starting at the position \(i\)_. In an overview [19], [PERSON] et al. discussed an algorithm based on an iterative application of [PERSON]'s Lyndon factorization algorithm [8], which we refer to here as _IDLA_, and an algorithmic scheme based on [PERSON] and [PERSON]'s work [20], which we refer to as _SSLA_. The authors were not aware of [PERSON]'s algorithm at that time. Two additional algorithms were presented there, a quadratic recursive application of [PERSON]'s algorithm and an algorithm \(NSV^{*}\) with possibly \(\mathcal{O}(n\ \log(n))\) worst-case complexity based on ranges that can be compared in constant time for constant alphabets. The correctness of \(NSV^{*}\) and its complexity were discussed there just informally. The algorithm _IDLA_ (see Figure 1) is simple and in-place, so no additional space is required except for the storage for the string and the Lyndon array. It is completely independent of the alphabet of the string and does not require the alphabet to be sorted; all it requires is that the alphabet be ordered,i.e., only pairwise comparisons of the alphabet symbols are needed. Its weakness is its quadratic worst-case complexity, which becomes a problem for longer strings with long right-maximal Lyndon substrings, as one of our experiments showed (see Figure 11 in Section 7). In our empirical work, we used _IDLA_ as a control for comparison and as a verifier of the results. Note that the reason the procedure _MaxLyn_ of Figure 1 really computes the longest Lyndon prefix is not obvious and is based on the properties of periods of prefixes; see [8] or Observation 6 and Lemma 11 in [19]. Lemma 1, below, characterizes right-maximal Lyndon substrings in terms of the relationships of the suffixes and follows from the work of [PERSON] and [PERSON] [20]. Though the definition of the proto-Lyndon substring is formally given in Section 2 below, it suffices to say the it means that it is a prefix of a Lyndon substring of the string. The definition of the lexicographic ordering \(\prec\) is also given Section 2. The proof of this lemma is delayed to the end of Section 2, where all the technical terms needed are defined. **Lemma 1**. : _Consider a string \(\mathbf{x}[1..n]\) over an alphabet ordered by \(\prec\). A substring \(\mathbf{x}[i..j]\) is proto-Lyndon if and only if:_  
_(a)_ \(\mathbf{x}[i..n]\prec\mathbf{x}[k..n]\) _for any_ \(i<k\leq j\) _._  
_A substring \(\mathbf{x}[i..j]\) is right-maximal Lyndon if and only if:_  
_(b)_ \(\mathbf{x}[i..n]\) _is proto-Lyndon and_  
_(c)_ _either_ \(j=n\) _or_ \(\mathbf{x}[j+1..n]\prec\mathbf{x}[i..n]\) _._  
Thus, the Lyndon array is an _NSV_ (_Next Smaller Value_) array of the inverse suffix array. Consequently, the Lyndon array can be computed by sorting the suffixes, i.e., computing the suffix array, then computing the inverse suffix array, and then applying _NSV_ to it; see [19]. Computing the inverse suffix array and applying _NSV_ are \"naturally\" linear, and computing the suffix array can be implemented to be linear; see [19; 21] and the references therein.