# Computing Maximal Lyndon Substrings of a String
## 4 The Algorithm _Bsla_
### The Refinement
Hence, \(i_{1},...,i_{v}\in H_{t+1}\), \(\mathcal{C}^{\prime}(i_{1})=...=\mathcal{C}^{\prime}(i_{v})=con^{\prime}(H_{ t+1})\), and \(j=\mathit{prev}^{\prime}(i)=\mathit{prev}^{\prime}(i_{1})=...=\mathit{prev} ^{\prime}(i_{v})\), and so, \(j<i_{1}\). It remains to show that \(\mathcal{C}^{\prime}(j)\mathcal{C}^{\prime}(i_{1})...\mathcal{C}^{\prime}(i_{ v})\) is a prefix of \(x[j..n]\). It suffices to show that \(\mathcal{C}^{\prime}(j)\) is immediately followed by \(\mathcal{C}^{\prime}(i_{1})\). If \(\mathcal{C}^{\prime}(j)\cap\mathcal{C}^{\prime}(i_{1})\
eq\emptyset\), then by the Monge property \((C_{8}),\mathcal{C}^{\prime}(i_{1})\subseteq\mathcal{C}^{\prime}(j)\) as \(j<i_{1}\), and so, by \((C_{7}(a))\), \(\mathit{con}^{\prime}(H_{t+1})\prec\mathit{con}^{\prime}(gr^{\prime}(i_{1}))= con^{\prime}(H_{t+1})\), a contradiction. Thus, \(\mathcal{C}^{\prime}(j)\cap\mathcal{C}^{\prime}(i_{1})=\emptyset\). Set \(j_{1}=j+|\mathit{con}^{\prime}(gr^{\prime}(j))|\). It follows that \(j_{1}\leq i_{1}\). Assume that \(j_{1}<i_{1}\). Since \(j=\mathit{prev}^{\prime}(i_{1})\) and \(j<i_{1}\), \(\mathit{con}^{\prime}(gr^{\prime}(j_{1}))\succeq\mathit{con}^{\prime}(gr^{ \prime}(i_{1}))=\mathit{con}^{\prime}(H_{t+1})\). Since \(j_{1}\
otin H_{t+1}\), \(\mathit{con}^{\prime}(gr^{\prime}(j_{1}))\succ\mathit{con}^{\prime}(H_{t+1})\). Consider \(\mathcal{C}^{\prime}(j_{1})\). If \(\mathcal{C}^{\prime}(j_{1})\cap\mathcal{C}^{\prime}(i_{1})\
eq\emptyset\), then by \((C_{8})\), \(\mathcal{C}^{\prime}(i_{1})\subseteq\mathcal{C}^{\prime}(j_{1})\), and so, by \((C_{7}(a))\), \(\mathit{con}^{\prime}(H_{t+1})\prec\mathit{con}^{\prime}(gr^{\prime}(i_{1}))= \mathit{con}^{\prime}(H_{t+1})\), a contradiction. Thus, \(\mathcal{C}^{\prime}(j_{1})\cap\mathcal{C}^{\prime}(i_{1})=\emptyset\). Since \(\mathcal{C}^{\prime}(j_{1})\) immediately follows \(\mathcal{C}^{\prime}(j)\), by \((C_{7}(b))\), \(\mathit{con}^{\prime}(gr^{\prime}(j_{1}))\preceq\mathit{con}^{\prime}(H_{t+1})\), a contradiction. Therefore, \(j_{1}=i_{1}\), and so, \(\mathit{prev}^{\prime}\) is proper on \(H_{t+1}\). This concludes the proof of Claim 3. **Claim 4**. : \(\boldsymbol{H_{t+1}}\) _is a complete group, i.e., \((C_{5})\) for \(\mathit{Conf}^{\prime}\) holds._  
Proof of Claim 4.: Assume that there is \(i\in H_{t+1}\) so that \(\mathcal{C}^{\prime}(i)\) is not maximal, i.e., for some \(k\geq i+|\mathit{con}^{\prime}(H_{t+1})|,\boldsymbol{x}[i..k]\) is a right-maximal Lyndon substring of \(\boldsymbol{x}\). Either \(k=n\) and so \(\mathit{con}^{\prime}(gr^{\prime}(k))=\boldsymbol{x}[k]\), and so, \(\mathcal{C}^{\prime}(k)\) is a suffix of \(\boldsymbol{x}[i..k]\), or \(k<n\), and then, \(\boldsymbol{x}[k+1]\prec\boldsymbol{x}[k]\), since \(\boldsymbol{x}[k+1]\preceq\boldsymbol{x}[k]\) implies that \(\boldsymbol{x}[i..k+1]\) is Lyndon, a contradiction with the right-maximality of \(\boldsymbol{x}[i..k]\). Consider \(\mathcal{C}^{\prime}(k)\), then \(\mathcal{C}^{\prime}(k)\subseteq\boldsymbol{x}[i..k]\), and so, \(\mathcal{C}^{\prime}(k)=\boldsymbol{x}[k]\). Therefore, there is \(j_{1}\) so that \(i+|\mathit{con}^{\prime}(H_{t+1})|\leq j_{1}\leq k\), and \(\mathcal{C}^{\prime}(j_{1})\) is a suffix of \(\boldsymbol{x}[i..k]\). Take the smallest such \(j_{1}\). If \(j_{1}=i+|\mathit{con}^{\prime}(H_{t+1})|\), then \(\mathcal{C}^{\prime}(i)\prec\mathcal{C}^{\prime}(j_{1})\) as \(\boldsymbol{x}[i..k]=\mathcal{C}^{\prime}(i)\mathcal{C}^{\prime}(j_{1})\) is Lyndon. By \((C_{7}(b))\), \(\mathcal{C}^{\prime}(j_{1})\preceq\mathit{con}^{\prime}(H_{t+1})\), so we have \(\mathit{con}^{\prime}(H_{t+1})=\mathcal{C}^{\prime}(i)\prec\mathcal{C}^{ \prime}(j_{1})\preceq\mathit{con}^{\prime}(H_{t+1})\), a contradiction. Therefore, \(j_{1}>i+|\mathit{con}^{\prime}(H_{t+1})|\). Consider \(x[j_{1}-1]\). If \(x[j_{1}-1]\preceq\boldsymbol{x}[j_{1}],\boldsymbol{x}[j_{1}-1..k]\) is Lyndon, and since \(\boldsymbol{x}[j_{1}..k]=\mathcal{C}^{\prime}(j_{1})\), \(\boldsymbol{x}[j_{1}-1..k]\) would be a context of \(g\prime(j_{1}-1)\), this contradicts the fact \(j_{1}\) was chosen to be the smallest such one.