# Computing Maximal Lyndon Substrings of a String
## 4 The Algorithm _Bsla_
### The Refinement
Case \(\mathcal{C}^{\prime}(i)=\mathcal{C}(i)\mathcal{C}(i_{1})..\mathcal{C}(i_{v})\) and \(\mathcal{C}^{\prime}(j)=\mathcal{C}(j)\mathcal{C}(j_{1})...\mathcal{C}(j_{w})\), where \(v=\mathit{val}(i_{1})\), \(\mathcal{C}(i_{1})=...=\mathcal{C}(i_{v})=\mathit{con}(G_{t})\), and \(i_{1}\approx...\approx i_{v}\) and where \(v=\mathit{val}(j_{1})\), \(\mathcal{C}(j_{1})=...=\mathcal{C}(j_{w})=\mathit{con}(G_{t})\), and \(j_{1}\approx...\approx j_{w}\). 1. Show that \((C_{\mathcal{T}}(a))\) holds. Let \(\mathcal{C}^{\prime}(j)\subsetneq\mathcal{C}^{\prime}(i)\). Then, either \(\mathcal{C}(j)\subseteq\mathcal{C}(i)\), and so, \(\mathit{con}(G_{t})\prec\mathit{con}(gr(j))\), implying that \(\mathcal{C}(j)\) is maximal contradicting \(\mathcal{C}(j)\mathcal{C}(j_{1})...\mathcal{C}(j_{w})\) being Lyndon. Thus, \(\mathcal{C}(j)\subsetneq\mathcal{C}(i_{\ell})\) for some \(1\leq\ell\leq v\). However, then, \(\mathit{con}(G_{t})\prec\mathit{con}(gr(j))\), implying that \(\mathcal{C}(j)\) is maximal, again a contradiction. This is an impossible case. 2. Show that \((C_{\mathcal{S}})\) holds. Let \(\mathcal{C}^{\prime}(i)\cap\mathcal{C}^{\prime}(j)\
eq\emptyset\). Let us first assume that \(\mathcal{C}(i)\cap\mathcal{C}(j)\
eq\emptyset\). Then, \(\mathcal{C}(j)\subseteq\mathcal{C}(i)\). Since \(\mathcal{C}(j)\) cannot be a suffix of \(\mathcal{C}(i)\), it follows that \(\mathcal{C}(i)\cap\mathcal{C}(j_{1})\
eq\emptyset\). Therefore, \(\mathcal{C}(j)\mathcal{C}(j_{1})\subseteq\mathcal{C}(i)\). Repeating this argument leads to \(\mathcal{C}(j)\mathcal{C}(j_{1})...\mathcal{C}(j_{w})\subseteq\mathcal{C}(i)\), and we are done. Therefore, assume that \(\mathcal{C}(i)\cap\mathcal{C}(j)=\emptyset\). Let \(1\leq\ell\leq v\) be the smallest such that \(\mathcal{C}(i_{\ell})\cap\mathcal{C}(j)\
eq\emptyset\). Such an \(\ell\) must exist. Then, \(i_{\ell}\leq j\). If \(i_{\ell}=j\), then either \(\mathcal{C}(i_{\ell})\) is a prefix of \(\mathcal{C}(j)\) or vice versa, both impossibilities; hence, \(i_{\ell}<j\). Repeating the same arguments as for \(i\), we get that \(\mathcal{C}(j)\mathcal{C}(j_{1})..\mathcal{C}(j_{w})\subseteq\mathcal{C}(i_{\ell})\), and so, we are done. It remains to show that \((C_{7}(b))\) for \(\mathit{Conf}^{\prime}\) holds. Consider \(\mathcal{C}^{\prime}(i)\) immediately followed by \(\mathcal{C}^{\prime}(j)\) with \(\mathcal{C}^{\prime}(i)\prec\mathcal{C}^{\prime}(j)\). 1. Assume that \(g\prime^{\prime}(j)\in\{G_{\text{t-1}},...,G_{1}\}\). Then, \(con(G_{t})=con^{\prime}(G_{t})\), \(g\prime(j)=g\prime^{\prime}(j)\), and \(con(gr(j))=con^{\prime}(gr^{\prime}(j))\). If \(\mathcal{C}^{\prime}(i)=\mathcal{C}(i)\), then \(\mathcal{C}(i)\prec\mathcal{C}(j)\), and \(\mathcal{C}(i)\) is immediately followed by \(\mathcal{C}(j)\), so by \((C_{7}(b))\) for \(\mathit{Conf}\), we have a contradiction. Thus, \(\mathcal{C}^{\prime}(i)=\mathcal{C}(i)\mathcal{C}(i_{1})...\mathcal{C}(i_{v})\) for \(v=val(i)\) and \(con(gr(i_{v}))=con(G_{t})\prec con(gr(j))\), and \(\mathcal{C}(i_{v})\) is immediately followed by \(\mathcal{C}(j)\), a contradiction by \((C_{7}(b))\) for \(\mathit{Conf}\). 2. Assume that \(g\prime^{\prime}(j)=G_{t}\). Then, the group \(gr(i)\) is partitioned when refining by \(G_{t}\), and so, \(\mathcal{C}^{\prime}(i)=con^{\prime}(gr^{\prime}(i))=con(gr(i))\mathcal{C}(j)^ {\circ}\) for \(v=val(j)\). Since \(\mathcal{C}^{\prime}(i)\) is immediately followed by \(\mathcal{C}^{\prime}(j)=con(G_{t})\), we have again a contradiction, as it implies that \(val(j)=v+1\). This concludes the proof of Claim 2. **Claim 3**. : _The function \(\mathit{prev}^{\prime}\) is proper on \(\boldsymbol{H_{t+1}}\), i.e., \((C_{6})\) for \(\mathit{Conf}^{\prime}\) holds._  
Proof of Claim 3.: Let \(j=\mathit{prev}^{\prime}(i)\) and \(i\in H_{t+1}\) with \(val^{\prime}(i)=v\). Then, \(|[i]_{\infty}|=v\), and so, \([i]_{\infty}=\{i_{1},...,i_{v}\}\), where \(i_{1}<i_{2}<...<i_{v}\).