# Computing Maximal Lyndon Substrings of a String
## 4 The Algorithm _Bsla_
### The Refinement  
For the sake of simplicity, we fix a string \(\boldsymbol{x}=\boldsymbol{x}[1..n]\) for the whole Section 4.2; all the definitions, lemmas, and theorems apply and refer to this \(\boldsymbol{x}\). **Lemma 9**. : _Let \(\mathcal{A}_{\boldsymbol{x}}=\{a_{1},...,a_{k}\}\) and \(a_{1}\prec a_{2}\prec...\prec a_{k}\). For \(1\leq\ell\leq k\), define \(G_{\ell}=\{i\in 1..n\mid\boldsymbol{x}[i]=a_{k+1-\ell}\}\) with context \(a_{k+1-\ell}\). Then, \(\langle G_{k},...,G_{1}\rangle\) is a one-complete group configuration._  
Proof. : \((C_{1})\), \((C_{2})\), \((C_{3})\), and \((C_{4})\) are straightforward to verify. To verify \((C_{5})\), we need to show that \(G_{1}\) is complete. Any occurrence of \(a_{k}\) in \(\boldsymbol{x}\) is a right-maximal Lyndon substring, so \(G_{1}\) is complete. To verify \((C_{6})\), consider \(j=prev(i)\) and \(val(i)=v\) for \(i\in G_{1}\). Consider any \(r\) such that \(j<r<i\). If \(\boldsymbol{x}[r]\
eq a_{k}\), then \(prev(i)<r\), which contradicts the definition of \(prev\). Hence, \(\boldsymbol{x}[r]=a_{k}\), and so, \(\boldsymbol{x}[j+1]=...=\boldsymbol{x}[i]=...\boldsymbol{x}[j+v+1]=a_{k}\), while \(\boldsymbol{x}[j]=a_{q}\) for some \(q<k\). It follows that \(\boldsymbol{x}[j..n]\) has \(a_{q}(a_{k})^{\triangledown}\) as a prefix. The condition \((C_{7}(a))\) is trivially satisfied as no \(\mathcal{C}(i)\) can have a proper substring. If \(\mathcal{C}(i)\) is immediately followed by \(\mathcal{C}(j)\) and \(\mathcal{C}(i)\prec\mathcal{C}(j)\), then \(\mathcal{C}(i)=\boldsymbol{x}[i]\), \(j=i+1\), \(\mathcal{C}(j)=\boldsymbol{x}[i+1]\), and \(\boldsymbol{x}[i]\prec\boldsymbol{x}[i+1]\). Then, \(con(\mathcal{C}(j))=\boldsymbol{x}[i+1]\preceq a_{k}=con(G_{1})\), so \((C_{7}(b))\) is also satisfied. To verify \((C_{8})\), consider \(\mathcal{C}(i)\cap\mathcal{C}(j)\
eq\emptyset\). Then, \(\mathcal{C}(i)=\boldsymbol{x}[i]=\boldsymbol{x}[j]=\mathcal{C}(j)\). Let \(\langle G_{k},...,G_{t},...,G_{1}\rangle\) by a \(t\)-complete group configuration. The refinement is driven by the group \(G_{t}\), and it might only partition the groups that precede it, i.e., the groups \(G_{k},...,G_{t+1}\), while the groups \(G_{t},...,G_{1}\) remain unchanged. * Partition \(G_{t}\) into classes of the equivalence \(\sim\). \(G_{t}=[i_{1}]\). \(\cup\)\([i_{2}]\). \(\cup\)\(\cup\)\(\cup\)\(\cup\)\([i_{p}]\). \(\cup\)\(\cup\)\(X\) where \(X=\{i\in G_{t}\mid prev(i)=nil\}\) may be possibly empty and \(i_{1}<i_{2}<...<i_{p}\). * Partition every class \([i_{\ell}]\)., \(1\leq\ell\leq p\), into classes of the equivalence \(\approx\). \([i_{\ell}]\). \(=[j_{\ell,1}]\).\(\cup\)\([j_{\ell,2}]\).\(\cup\)\(...\cup\)\([j_{\ell,m_{\ell}}]\).\(\cup\)\(\cup\)\([j_{\ell,m_{\ell}}]\). where \(val(j_{\ell,1})<val(j_{\ell,2})<...<val(j_{\ell,m_{\ell}})\). * Therefore, we have a list of classes in this order: \([j_{1,1}]\).\({}_{\approx}\), \([j_{1,2}]\).\({}_{\approx}\),... \([j_{1,m_{1}}]\).\({}_{\approx}\), \([j_{2,1}]\).\({}_{\approx}\), \([j_{2,2}]\).\({}_{\approx}\),..., \([j_{p,1}]\).\({}_{\approx}\), \([j_{p,2}]\).\({}_{\approx}\). This list is processed from left to right. Note that for each \(i\in[j_{\ell,\ell}]\). \(prev(i)\in gr(j_{\ell,k})\), and \(val(i)=val(j_{\ell,k})\). For each \(j_{\ell,k}\), move all elements \(\{prev(i)\mid i\in[j_{\ell,k}]\}\) from the group \(gr(prev(i_{\ell,k}))\) into a newgroup \(H\), place \(H\) in the list of groups right after the group \(gr(prev(j_{\ell,k}))\), and set its context to \(con(gr(prev(j_{\ell,k})))con(gr(j_{\ell,\ell}))^{val(j_{\ell,k})}\). (_Note, that this \"doubling of the contexts\" is possible due to \((C_{6})\)_). Then, update _prev_:  
All values of _prev_ are correct except possibly the values of _prev_ for indices from \(H\). It may be the case that for \(i\in H\), there is \(i^{\prime}\in gr(j_{\ell,k})\), so that \(prev(i)<i^{\prime}\), so \(prev(i)\) must be reset to the maximal such \(i^{\prime}\).