# Computing Maximal Lyndon Substrings of a String
## 4 The Algorithm _Bsla_
### Notation and Basic Notions of BSLA  
For the sake of simplicity, we fix a string \(\mathbf{x}=\mathbf{x}[1..n]\) for the whole Section 4.1; all the definitions and the observations apply and refer to this \(\mathbf{x}\). A _group_\(G\) is a non-empty set of indices of \(\mathbf{x}\). The group \(G\) is assigned a _context_, i.e., a substring \(\mathbf{con(G)}\) of \(\mathbf{x}\) with the property that for any \(i\in G\), \(\mathbf{x}[i..i+|con(G)|-1]=con(G)\). If \(i\in G\), then \(\mathbf{C(i)}\) denotes the occurrence of the context of \(G\) at the position \(i\), i.e., the substring \(\mathcal{C}(i)=\mathbf{x}[i..i+|con(G)|-1]\). We say that a group \(G^{\prime}\) is _smaller than_ or _precedes_ a group \(G^{\prime\prime}\) if \(con(G^{\prime})\prec on(G^{\prime\prime})\). Definition 1: An ordered list of groups \(\langle G_{k},G_{k-1},...,G_{2},G_{1}\rangle\) is a _group configuration_ if:  
\((C_{1})\): \(G_{k}\cup G_{k-1}\cup...\cup G_{2}\cup G_{1}=1..n\);  
\((C_{2})\): \(G_{j}\cap G_{\ell}=\emptyset\) for any \(1\leq\ell<j\leq k\);  
\((C_{3})\): \(con(G_{k})\prec on(G_{k-1})\prec...\prec on(G_{2})\prec on(G_{1})\);  
\((C_{4})\): _For any \(j\in 1..k\), \(con(G_{j})\) is a Lyndon substring of \(\mathbf{x}\)._  
Note that \((C_{1})\) and \((C_{2})\) guarantee that \(\langle G_{k},G_{k-1},...,G_{2},G_{1}\rangle\) is a disjoint partitioning of \(1..n\). For \(i\in\{1,..,n\}\), \(\mathbf{gr(i)}\) denotes the unique group to which \(i\) belongs, i.e., if \(i\in G_{t}\), then \(gr(i)=G_{t}\). Note that using this notation, \(\mathcal{C}(i)=\mathbf{x}[i..i+|con(gr(i))|-1]\). The mapping \(\mathbf{prev}\) is defined by \(\mathbf{prev}(i)=\max\{j<i\mid con(gr(j))\prec con(gr(i))\}\) if such \(j\) exists, otherwise \(\mathbf{prev}(i)=nil\). For a group \(G\) from a group configuration, we define an equivalence \(\mathbf{\sim}\) on \(G\) as follows: \(i\sim j\) iff \(gr(\mathbf{prev}(i))=gr(\mathbf{prev}(j))\) or \(\mathbf{prev}(i)=\mathbf{prev}(j)=nil\). The symbol \([i]_{\sim}\) denotes the class of equivalence \(\sim\) that contains \(i\), i.e., \([i]_{\sim}=\{j\in G\mid j\sim i\}\). If \(\mathbf{prev}(i)=nil\), then the class \([i]_{\sim}\) is called trivial. An interesting observation states that if \(G\) is viewed as an ordered set of indices, then a non-trivial \([i]_{\sim}\) is an interval:  
Observation 7: Let \(G\) be a group from a group configuration for \(\mathbf{x}\). Consider an \(i\in G\) such that \(\mathbf{prev}(i)\
eq nil\). Let \(j_{1}=\min[i]_{\sim}\) and \(j_{2}=\max[i]_{\sim}\). Then, \([i]_{\sim}=\{j\in G\mid j_{1}\leq j\leq j_{2}\}\). Proof: Since \(\mathbf{prev}(j_{1})\) is a candidate to be \(\mathbf{prev}(j)\), \(\mathbf{prev}(j)\
eq nil\) and \(\mathbf{prev}(j_{1})\leq\mathbf{prev}(j)\leq\mathbf{prev}(j_{2})=\mathbf{prev}(j_{1})\), so \(\mathbf{prev}(j)=\mathbf{prev}(j_{1})=\mathbf{prev}(j_{2})\). On each non-trivial class of \(\sim\), we define a relation \(\mathbf{\approx}\) as follows: \(i\approx j\) iff \(|j-i|=|con(G)|\); in simple terms, it means that the occurrence \(\mathcal{C}(i)\) of \(con(G)\) is immediately followed by the occurrence \(\mathcal{C}(j)\) of \(con(G)\). The transitive closure of \(\approx\) is a relation of equivalence, which we also denote by \(\mathbf{\approx}\). The symbol \([i]_{\approx}\) denotes the class of equivalence \(\approx\) containing \(i\), i.e., \([i]_{\approx}=\{j\in[i]_{\sim}\mid j\approx i\}\). For each \(j\) from a non-trivial \([i]_{\sim}\), we define the _valence_ by \(\mathbf{val(j)}=|[i]_{\approx}|\). In simple terms, \(val(i)\) is the number of elements from \([i]_{\sim}\) that are \(\approx i\). Thus, \(1\leq val(i)\leq|G|\). Interestingly, if \(G\) is viewed as an ordered set of indices, then \([i]_{\approx}\) is a subinterval of the interval \([i]_{\sim}\):  
Observation 8: Let \(G\) be a group from a group configuration for \(\mathbf{x}\). Consider an \(i\in G\) such that \(\mathbf{prev}(i)\
eq nil\). Let \(j_{1}=\min[i]_{\sim}\) and \(j_{2}=\max[i]_{\sim}\). Then, \([i]_{\sim}=\{j\in[i]_{\sim}\mid j_{1}\leq j\leq j_{2}\}\).