# Computing Maximal Lyndon Substrings of a String
## 3 \(\mathbf{\top}\)-Reduction Algorithm (Tkla)
### Properties Preserved by \(\mathbf{\Upsilon}\)-Reduction  
The most important property of \(\tau\)-reduction is a preservation of right-maximal Lyndon substrings of \(\mathbf{x}\) that start at black positions. This means there is a closed formula that gives, for every right-maximal Lyndon substring of \(\tau(\mathbf{x})\), a corresponding right-maximal Lyndon substring of \(\mathbf{x}\). Moreover, the formula for any black position can be computed in constant time. It is simpler to present the following results using \(\mathcal{L}^{\prime}\), the alternative form of the Lyndon array, the one where the end positions of right-maximal Lyndon substrings are stored rather than their lengths. More formally:  
**Theorem 2**. : _Let \(\mathbf{x}=\mathbf{x}[1..n]\); let \(\mathcal{L}^{\prime}_{\tau(\mathbf{x})}[1..m]\) be the Lyndon array of \(\tau(\mathbf{x})\); and let \(\mathcal{L}^{\prime}_{\mathbf{x}}[1..n]\) be the Lyndon array of \(\mathbf{x}\)._  
_Then, for any black \(i\in 1..n\), \(\mathcal{L}^{\prime}_{\mathbf{x}}[i]= \begin{cases}b(r)&\text{if }b(r)=n\;\;\text{or}\;\;\mathbf{x}[b(r)+1] \preceq\mathbf{x}[i]\\ b(r)+1&\text{otherwise,}\end{cases} \)_  
_where \(r=\mathcal{L}^{\prime}_{\tau(\mathbf{x})}[t(i)]\)._  
The proof of the theorem requires a series of lemmas that are presented below. First, we show that \(\tau\)-reduction preserves the relationships of certain suffixes of \(\mathbf{x}\). **Lemma 4**. : _Let \(\mathbf{x}=\mathbf{x}[1..n]\), and let \(\tau(\mathbf{x})=\tau(\mathbf{x})[1..m]\). Let \(i\
eq j\) and \(1\leq i,j\leq n\). If \(i\) and \(j\) are both black positions, then \(\mathbf{x}[i..n]\prec\mathbf{x}[j..n]\) implies \(\tau(\mathbf{x})[t(i)..m]\prec\tau(\mathbf{x})[t(j)..m]\)._  
Proof. : Since \(i\) and \(j\) are both black positions, both \(t(i)\) and \(t(j)\) are defined, and \(t(i)\
eq t(j)\). Let us assume that \(\mathbf{x}[i..n]\prec\mathbf{x}[j..n]\). The proof is argued in several cases determined by the nature of the relationship \(\mathbf{x}[i..n]\prec\mathbf{x}[j..n]\). 1. Case: \(\mathbf{x}[i..n]\) is a proper prefix of \(\mathbf{x}[j..n]\). Then, \(|\mathbf{x}[i..n]|=n-i+1<|\mathbf{x}[j..n]|=n-j+1\), and so, \(j<i\). It follows that \(\mathbf{x}[j..j+n-i]=\mathbf{x}[i..n]\), and thus, \(\mathbf{x}[i..n]\) is a border of \(\mathbf{x}[j..n]\). 1. Case: \(j+n-i\) is black. Since \(n\) may be either black or white, we need to discuss two cases. 1. Case: \(n\) is white. Since \(n\) is white, the last \(\tau\)-pair of \(\mathbf{x}\) must be \((n-1,n)\). The \(\tau\)-pairs of \(\mathbf{x}[j..j+n-i]\) must be the same as the \(\tau\)-pairs of \(\mathbf{x}[i..n]\); the last \(\tau\)-pair of \(\mathbf{x}[j..j+n-i]\) must  
\(\tau(x)[t(j+\ell-2)+1]=p(j+\ell,j+\ell+1)\). Since \(x[i+\ell-1]=x[j+\ell-1]\) and, by our Assumption (3), \(x[i+\ell]\prec\pi[j+\ell]\), \((x[i+\ell],x[i+\ell-1])\prec(x[j+\ell],x[j+\ell-1])\), giving \(p(i+\ell,i+\ell+1)\prec p(j+\ell,j+\ell+1)\), \(\tau(x)[t(i+\ell)]\prec\tau(x)[t(j+\ell)]\), and ultimately, \(\tau(x)[t(i+\ell-2)+1]=\tau(x)[t(i+\ell)]\prec\tau(x)[t(j+\ell)]=\tau(x)[t(j+ \ell-2)+1]\). It follows that \(\tau(x)[t(i)..m]\prec\tau(x)[t(j)..m]\). Lemma 5 shows that \(\tau\)-reduction preserves the proto-Lyndon property of certain proto-Lyndon substrings of \(x\). Lemma 5: _Let \(x=x[1..n]\), and let \(\tau(x)=\tau(x)[1..m]\). Let \(1\leq i<j\leq n\). Let \(x[i..j]\) be a proto-Lyndon substring of \(x\), and let \(i\) be a black position._  
\[\text{Then, } \begin{cases}\tau(x)[t(i)..t(j)]\text{ is proto-Lyndon}&\text{if $j$ is black}\\ \tau(x)[t(i)..t(j-1)]\text{ is proto-Lyndon}&\text{if $j$ is white.}\end{cases} \]  
Proof: Let us first assume that \(j\) is black. Since both \(i\) and \(j\) are black, \(t(i)\) and \(t(j)\) are defined. Let \(i_{1}=t(i)\), \(j_{1}=t(j)\), and consider \(k_{1}\), so that \(i_{1}<k_{1}\leq j_{1}\). Let \(k=b(k_{1})\). Then, \(t(k)=k_{1}\) and \(i<k\leq j\), and so, \(x[i..n]\prec x[k..n]\) by Lemma 1 as \(x[i..j]\) is proto-Lyndon. It follows that \(\tau(x)[t(i)..m]\prec\tau(x)[t(k)..m]\) by Lemma 4.