# Computing Maximal Lyndon Substrings of a String
## 2 Basic Notation and Terminology
The order is extended to all finite strings over the alphabet \(\mathcal{A}\): for \(\mathbf{x}=\mathbf{x}[1..n]\) and \(\mathbf{y}=\mathbf{y}[1..n]\), \(\mathbf{x}\prec\mathbf{y}\) if either \(\mathbf{x}\) is a proper prefix of \(\mathbf{y}\) or there is a \(j\leq\min\{n,m\}\) so that \(\mathbf{x}[1]=\mathbf{y}[1]\),..., \(\mathbf{x}[j-1]=\mathbf{y}[j-1]\) and \(\mathbf{x}[j]\prec\mathbf{y}[j]\). This total order induced by the order of the alphabet is called a _lexicographic_ order of all non-empty strings over \(\mathcal{A}\). We denote by \(\mathbf{x}\preceq\mathbf{y}\) if either \(\mathbf{x}\prec\mathbf{y}\) or \(\mathbf{x}=\mathbf{y}\). A string \(\mathbf{x}\) over \(\mathcal{A}\) is _Lyndon_ for a given order \(\prec\) of \(\mathcal{A}\) if \(\mathbf{x}\) is strictly lexicographically smaller than any non-trivial rotation of \(\mathbf{x}\). In particular:  
\[\mathbf{x}\text{ is Lyndon}\Rightarrow\mathbf{x}\text{ is unbordered}\Rightarrow\mathbf{x} \text{ is primitive}\]  
Note that the reverse implications do not hold: _aba_ is primitive but neither unbordered, nor Lyndon, while _acaab_ is unbordered, but not Lyndon. A substring \(\mathbf{x}[i..j]\) of \(\mathbf{x}[1..n]\), \(1\leq i\leq j\leq n\) is a _right-maximal Lyndon substring of \(\mathbf{x}\)_ if it is Lyndon and either \(j=n\) or for any \(k>j\), \(\mathbf{x}[i..k]\) is not Lyndon. A substring \(\mathbf{x}[i..j]\) of a string \(\mathbf{x}[1..n]\) is _proto-Lyndon_ if there is a \(j\leq k\leq n\) so that \(\mathbf{x}[i..k]\) is Lyndon. The _Lyndon array_ of a string \(\mathbf{x}=\mathbf{x}[1..n]\) is an integer array \(\mathcal{L}[1..n]\) so that \(\mathcal{L}[i]=j\) where \(j\leq n-i\) is a maximal integer such that \(\mathbf{x}[i..i+j-1]\) is Lyndon. Alternatively, we can define it as an integer array \(\mathcal{L}^{\prime}[1..n]\) so that \(\mathcal{L}^{\prime}[i]=j\) where \(j\) is the last position of the right-maximal Lyndon substring starting at the position \(i\). The relationship between those two definitions is straightforward: \(\mathcal{L}^{\prime}[i]=\mathcal{L}[i]+i-1\) or \(\mathcal{L}[i]=\mathcal{L}^{\prime}[i]-i+1\). Proof of Lemma 1.: We first prove the following claim:  
_Claim. Substring \(\mathbf{x}[i..j]\) is right-maximal Lyndon if and only if:_  
\[ \begin{array}{ll}(b^{\prime})&\mathbf{x}[i..n]\prec\mathbf{x}[k..n]\text{ }for\ any\ i<k\leq j\text{ and }\\ (c\ )&\text{either }j=n\text{ or }\mathbf{x}[j+1..n]\prec\mathbf{x}[i..n].\end{array} \]  
Let \(\mathbf{x}[i..j]\) be right-maximal Lyndon. We need to show that \((b^{\prime})\) and \((c)\) hold. Let \(i<k\leq j\). Since it is Lyndon, \(\mathbf{x}[i..j]\prec\mathbf{x}[k..j]\). Thus, there is \(0\leq r\) so that \(i+r\leq j\) and \(j+r\leq j\) and \(\mathbf{x}[i+\ell]=\mathbf{x}[j+\ell]\) for any \(0\leq\ell<r\) and \(\mathbf{x}[i+r]\prec\mathbf{x}[j+r]\). It follows that \(\mathbf{x}[i..n]\prec\mathbf{x}[j..n]\), and \((b^{\prime})\) is satisfied. If \(j=n\), then \((c)\) holds. Therefore, let us assume that \(j<n\). (1) If \(\mathbf{x}[i]\prec\mathbf{x}[j+1]\), then \(\mathbf{x}[i..j+1]\prec\mathbf{x}[j+1..j+1]\); together with \(\mathbf{x}[i..j]\prec\mathbf{x}[k..j]\) for any \(i<k\leq j\), it shows that \(\mathbf{x}[i..j+1]\) is Lyndon, contradicting the right-maximality of \(\mathbf{x}[i..j]\). (2) If \(\mathbf{x}[i]\succ\mathbf{x}[j+1]\), then \(\mathbf{x}[i..n]\succ\mathbf{x}[j+1..n]\), and \((c)\) holds. (3) If \(\mathbf{x}[i]=\mathbf{x}[j+1]\), then there are a prefix \(\mathbf{u}\), strings \(\mathbf{v}\) and \(\mathbf{w}\), and an integer \(r\geq 1\) so that \(\mathbf{uv}=\mathbf{x}[i..j]\), \(\mathbf{x}[i..n]=\mathbf{uvw}^{\prime}\mathbf{w}\), and \(\mathbf{x}[j+1..n]=\mathbf{u}^{\prime}\mathbf{w}\). Let us take a maximal such \(\mathbf{u}\) and a maximal such \(r\). Let \(r\geq 2\). Then, since \(\mathbf{uv}=\mathbf{x}[i..j]\) is Lyndon, \(\mathbf{u}\prec\mathbf{v}\), and so, \(\mathbf{uu}\prec\mathbf{uv}\); hence, \(\mathbf{u}^{\prime}\mathbf{w}\prec\mathbf{uv}^{\prime}\mathbf{w}\), and \((c)\) holds.