# Computing Maximal Lyndon Substrings of a String
## 3 \(\mathbf{\top}\)-Reduction Algorithm (Tkla)  
The purpose of this section is to introduce a recursive algorithm _Tkla_ for computing the Lyndon array of a string. As will be shown below, the most significant aspect is the so-called \(\tau\)-reduction of a string and how the Lyndon array of the \(\tau\)-reduced string can be expanded to a partially filled Lyndon array for the whole string, as well as how to compute the missing values. This section thus provides the mathematical justification for the algorithm and, in so doing, proves the correctness of the algorithm. The mathematical understanding of the algorithm provides the bases for the bounding of its worst-case complexity by \(O(n\log(n))\) and determining the linearity of the average-case complexity.  
The first idea of the algorithm was proposed in [PERSON]'s 2017 Ph.D. thesis [36]. It follows [PERSON]'s approach [25]:  
1. reduce the input string \(\mathbf{x}\) to \(\mathbf{y}\);
2. by recursion, compute the Lyndon array of \(\mathbf{y}\); and
3. from the Lyndon array of \(\mathbf{y}\), compute the Lyndon array of \(\mathbf{x}\).  
The input strings for the algorithm are \(\$\)-terminated strings over an integer alphabet. The reduction computed in (1) is important. All linear algorithms for suffix array computations use the proximity property of suffixes: comparing \(\mathbf{x}[i..n]\) and \(\mathbf{x}[j..n]\) can be done by comparing \(\mathbf{x}[i]\) and \(\mathbf{x}[j]\) and, if they are the same, comparing \(\mathbf{x}[i+1..n]\) with \(\mathbf{x}[j+1..n]\). For instance, in the first linear algorithm for the suffix array by [PERSON] and [PERSON] [37], obtaining the sorted suffixes for positions \(i\equiv 0\pmod{3}\) and \(i\equiv 1\pmod{3}\) via the recursive call is sufficient to determine the order of suffixes for the \(i\equiv 2\pmod{3}\) positions, then merging both lists together. However, there is no such proximity property for right-maximal Lyndon substrings, so the reduction itself must have a property that helps determine some of the values of the Lyndon array of \(\mathbf{x}\) from the Lyndon array of \(\mathbf{y}\) and computing the rest.  
In our algorithm, we use a special reduction, which we call \(\tau\)-reduction, defined in Section 3.2, that reduces the original string to at most \(\frac{1}{2}\) and at least \(\frac{2}{3}\) of its length. The algorithm computes \(\mathbf{y}\) as a \(\tau\)-reduction of the input string \(\mathbf{x}\) in Step (1) in linear time. In Step (3), it expands the Lyndon array of the reduced string computed by Step (2) to an incomplete Lyndon array of the original string also in linear time. The incomplete Lyndon array computed in (3) is about \(\frac{1}{2}\) to \(\frac{2}{3}\) full, and for every position \(i\) with an unknown value, the values at positions \(i-1\) and \(i+1\) are known. In particular, the values at Position 1 and position \(n\) are both known. Therefore, much information is provided by the recursive Step (2). For instance, for \(00011001\), via the recursive call, we would identify the right-maximal Lyndon substrings that are underlined in \(00011001\) and would need to compute the missing right-maximal Lyndon substrings that are underlined in \(00011001\).  
However, computing the missing values of the incomplete Lyndon array takes at most \(O(n\ \log(n))\) steps, as we will show, resulting in the overall worst-case complexity of \(O(n\ \log(n))\). When the input string is such that the missing values of the incomplete Lyndon array of the input string can be computed in linear time, the overall execution of the algorithm is linear as well, and thus, the average case complexity will be shown to be linear in the length of the input string.  
In the following subsections, we describe the \(\tau\)-reduction in several steps: first, the \(\tau\)-pairing, then choosing the \(\tau\)-alphabet, and finally, the computation of the \(\tau(\mathbf{x})\). The \(\tau\)-reduction may be of some general interest as it preserves (see Lemma 6) some right-maximal Lyndon substrings of the original string.