# Computing Maximal Lyndon Substrings of a String
## 3 \(\mathbf{\top}\)-Reduction Algorithm (Tkla)
### Properties Preserved by \(\mathbf{\Upsilon}\)-Reduction
Let \((*)\) denote the condition from the theorem, i.e.,  
\(b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]\big{)}=n\) or \(x\big{[}b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]\big{)}+1\big{]} \preceq x[i]\)  
(1) Case: \(j\) is black. Then, by Lemma 6, \(\tau(x)[t(i)..t(j)]\) is a right-maximal Lyndon substring of \(\tau(x)\); hence, \(\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]=t(j)\). Therefore, \(b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]\big{)}=b(t(j))=j=\mathcal{ L}^{\prime}_{\mathbf{X}}[i]\). We have to also prove that the condition \((*)\) holds. If \(j=n\), then the condition \((*)\) holds. Therefore, assume that \(j<n\). Since \(x[i..j]\) is right-maximal, by Lemma 1, \(x[j+1..n]\prec x[i..n]\), and so, \(x[j+1]\preceq x[i]\). Then, \(x[b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]\big{)}+1]=x[b(t(j))+1]=x[j+1]\preceq x[i]\). (2) Case: \(j\) is white. Then, \(j-1\) is black, and \(\tau(x)[t(j-1)]=p(j-1,j)\). By Lemma 6, \(\tau(x)[t(i)..t(j-1)]\) is a right-maximal Lyndon substring of \(\tau(x)\); hence, \(\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]=t(j-1)\), so \(b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]=b(t(j-1))=j-1\), giving \(b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]+1\big{)}=j\). We want to show that the condition \((*)\) does not hold. If \(b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]\big{)}=n\), then \(j-1=n\), which is impossible as \(j\leq n\). Since \(x[i..j]\) is Lyndon, \(x[i]\prec x[j]\), and so, \(x[i]\prec\tau[b\big{(}\mathcal{L}^{\prime}_{\tau(\mathbf{X})}[t(i)]+1\big{)}\big{]}\). Thus, Condition \((*)\) does not hold. \(\Box\)  
Computing \(\mathcal{L}^{\prime}_{\mathbf{X}}\) from \(\mathcal{L}^{\prime}_{\tau(\mathbf{X})}\)  
Theorem 2 indicates how to compute the partial \(\mathcal{L}^{\prime}_{\mathbf{X}}\) from \(\mathcal{L}^{\prime}_{\tau(\mathbf{X})}\). The procedure is given in Figure 3.  
To compute the missing values, the partial array is processed from right to left. When a missing value at position \(i\) is encountered (note that it is recognized by \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]=nil\)), the Lyndon array \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1..n]\) is completely filled, and also, \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{-}1]\) is known. Recall that \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1]\) is the ending position of the right-maximal Lyndon substring starting at the position \(i{+}1\). In several cases, we can determine the value of \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]\) in constant time:  
1. if \(i=n\), then \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]=i\). 2. if \(\mathbf{x}[i]\succ\mathbf{x}[i{+}1]\), then \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]=i\). 3. if \(\mathbf{x}[i]=\mathbf{x}[i{+}1]\) and \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1]=i{+}1\) and either \(i{+}1=n\) or \(i{+}1=\mathcal{L}^{\prime}_{\mathbf{x}}[i{-}1]\), then \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]=i\). 4. if \(\mathbf{x}[i]\prec\mathbf{x}[i{+}1]\) and \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1]=i{+}1\) and either \(i{+}1=n\) or \(i{+}1=\mathcal{L}^{\prime}_{\mathbf{x}}[i{-}1]\), then \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]=i{+}1\). 5. if \(\mathbf{x}[i]\preceq\mathbf{x}[i{+}1]\) and \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1]>i{+}1\) and either \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1]=n\) or \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1]=\mathcal{L}^{\prime}_{\mathbf{x}}[i{-}1]\), then \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]=\mathcal{L}^{\prime}_{\mathbf{x}}[i{+}1]\). We call such points _easy_. All others will be referred to as _hard_. For a _hard_ point \(i\), it means that \(\mathbf{x}[i]\) is followed by at least two consecutive right-maximal Lyndon substrings before reaching either \(\mathcal{L}^{\prime}_{\mathbf{x}}[i{-}1]\) or \(n\), and we might need to traverse them all. The **while** loop, seen in Figure 4's procedure, is the likely cause of the \(\mathcal{O}(n\,\log(n))\) complexity.