# Computing Maximal Lyndon Substrings of a String
## 2 Basic Notation and Terminology  
Most of the fundamental notions, definitions, facts, and string algorithms can be found in [31; 32; 33; 34]. For the ease of access, this section includes those that are directly related to the work herein. The set of integers is denoted by \(\mathbb{Z}\). For two integers \(i\leq j\), the _range_\(i..j=\{k\in\mathbb{Z}\;|\;i\leq k\leq j\}\). An _alphabet_ is a finite or infinite set of _symbols_, or equivalently called _letters_. We always assume that the sentinel symbol \(\mathfrak{S}\) is not in the alphabet and is always assumed to be lexicographically the smallest. A _string_ over an alphabet \(\mathcal{A}\) is a finite sequence of symbols from \(\mathcal{A}\). A \(\mathfrak{S}\)-_terminated string_ over \(\mathcal{A}\) is a string over \(\mathcal{A}\) terminated by \(\mathfrak{S}\). We use the array notation indexing from \(1\) for strings; thus, \(\boldsymbol{x}[1..n]\) indicates a string of length \(n\); the first symbol is the symbol with index \(1\), i.e., \(\boldsymbol{x}[1]\); the second symbol is the symbol with index \(2\), i.e., \(\boldsymbol{x}[2]\), etc. Thus, \(\boldsymbol{x}[1..n]=\boldsymbol{x}[1]\boldsymbol{x}[2]...\boldsymbol{x}[n]\). For a \(\mathfrak{S}\)-terminated string \(\boldsymbol{x}\) of length \(n\), \(\boldsymbol{x}[n{+}1]=\mathfrak{S}\). The _alphabet of string \(\boldsymbol{x}\)_, denoted as \(\mathcal{A}_{\boldsymbol{x}}\), is the set of all distinct alphabet symbols occurring in \(\boldsymbol{x}\). We use the term _strings over a constant alphabet_ if the alphabet is a fixed finite alphabet. The _integer alphabet_ is the infinite alphabet \(\mathcal{A}=\{0,1,2,...\}\). We use the term _strings over integer alphabet_ for the strings over the alphabet \(\{0,1,2,...\}\) with an additional constraint that all letters occurring in the string are all smaller than the length of the string, i.e., in this paper, \(\boldsymbol{x}[1..n]\) is a string over the integer alphabet if it is a string over the alphabet \(\{0,1,...n{-}1\}\). Many authors use a more general definition; for instance, [PERSON] and [PERSON] [35] defined it as any set of integers of size \(n^{o(1)}\); however, our results can easily be adapted to such more general definitions without changing their essence. We use a _bold font_ to denote strings; thus, \(x\) denotes a string, while \(x\) denotes some other mathematical entity such as an integer. The _empty string_ is denoted by \(\varepsilon\) and has length zero. The _length_ or _size_ of string \(x=x[1..n]\) is \(n\). The length of a string \(x\) is denoted by \(|x|\). For two strings \(x=x[1..n]\) and \(y=y[1..m]\), the _concatenation_\(xy\) is a string \(u\)  
\[\text{where }\mathbf{u}[i]= \begin{cases}\mathbf{x}[i]\text{ }for\ i\leq n,\\ \mathbf{y}[i-n]\text{ }for\ n<i\leq n+m.\end{cases} \]  
If \(\mathbf{x}=\mathbf{uvw}\), then \(\mathbf{u}\) is a _prefix_, \(\mathbf{v}\) a _substring_, and \(\mathbf{w}\) a _suffix_ of \(x\). If \(\mathbf{u}\) (respectively, \(\mathbf{v}\), \(\mathbf{w}\)) is empty, then it is called an _empty prefix_ (respectively, _empty substring, empty suffix_); if \(|\mathbf{u}|<|x|\) (respectively, \(|\mathbf{v}|<|\mathbf{x}|\), \(|\mathbf{w}|<|\mathbf{x}|\)), then it is called a _proper prefix_ (respectively, _proper substring_, _proper suffix_). If \(\mathbf{x}=\mathbf{uv}\), then \(\mathbf{vu}\) is called a _rotation_ or a _conjugate_ of \(\mathbf{x}\); if either \(\mathbf{u}=\varepsilon\) or \(\mathbf{v}=\varepsilon\), then the rotation is called _trivial_. A non-empty string \(x\) is _primitive_ if there is no string \(y\) and no integer \(k\geq 2\) so that \(\mathbf{x}=\mathbf{y}^{k}=\underbrace{yy\cdots y}_{k\text{ }times}\). A non-empty string \(x\) has a non-trivial border \(\mathbf{u}\) if \(\mathbf{u}\) is both a non-empty proper prefix and a non-empty proper suffix of \(x\). Thus, both \(\varepsilon\) and \(\mathbf{x}\) are trivial borders of \(x\). A string without a non-trivial border is call _unbordered_. Let \(\prec\) be a total order of an alphabet \(\mathcal{A}\).