# Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings +
## 3 Duval's Algorithm  
In this section we briefly describe [PERSON]'s algorithm for the computation of the Lyndon factorization of a word. Let \(L\) be the set of Lyndon words and let  
\[P=\{w\mid w\in\Sigma^{+}\text{ and }w\Sigma^{*}\cap L\
eq\emptyset\}\,,\]  
be the set of nonempty prefixes of Lyndon words. Let also \(P^{\prime}=P\cup\{c^{k}\mid k\geq 2\}\), where \(c\) is the maximum symbol in \(\Sigma\). [PERSON]'s algorithm is based on the following Lemmas, proved in [5]:  
**Lemma 1**. : _Let \(w\in\Sigma^{+}\) and \(w_{1}\) be the longest prefix of \(w=w_{1}w^{\prime}\) which is in \(L\). We have \(CFL(w)=w_{1}CFL(w^{\prime})\)._  
**Lemma 2**. : \(P^{\prime}=\{(uv)^{k}u\mid u\in\Sigma^{*},v\in\Sigma^{+},k\geq 1\text{ and }uv\in L\}\)_._  
**Lemma 3**. : _Let \(w=(uav^{\prime})^{k}u\), with \(u,v^{\prime}\in\Sigma^{*}\), \(a\in\Sigma\), \(k\geq 1\) and \(uav^{\prime}\in L\). The following propositions hold:_  
1. _For_ \(a^{\prime}\in\Sigma\) _and_ \(a>a^{\prime}\)_,_ \(wa^{\prime}\
otin P^{\prime}\)_;_
2. _For_ \(a^{\prime}\in\Sigma\) _and_ \(a<a^{\prime}\)_,_ \(wa^{\prime}\in L\)_;_
3. _For_ \(a^{\prime}=a\)_,_ \(wa^{\prime}\in P^{\prime}\setminus L\)_._  
Lemma 1 states that the computation of the Lyndon factorization of a word \(w\) can be carried out by computing the longest prefix \(w_{1}\) of \(w=w_{1}w^{\prime}\) which is a Lyndon word and then recursively restarting the process from \(w^{\prime}\). Lemma 2 states that the nonempty prefixes of Lyndon words are all of the form \((uv)^{k}u\), where \(u\in\Sigma^{*},v\in\Sigma^{+},k\geq 1\) and \(uv\in L\). By the first property of Lyndon words, the longest prefix of \((uv)^{k}u\) which is in \(L\) is \(uv\). Hence, if we know that \(w=(uv)^{k}uav^{\prime},(uv)^{k}u\in P^{\prime}\) but \((uv)^{k}ua\
otin P^{\prime}\), then by Lemma 1 and by induction we have \(CFL(w)=w_{1}w_{2}\ldots w_{k}CFL(uav^{\prime})\), where \(w_{1}=w_{2}=\ldots=w_{k}=uv\). For example, if \(w=abababba\), we have \(CFL(w)=abb\)\(abb\)\(CFL(aba)\), since \(abababab\in P^{\prime}\) while \(abababba\
otin P^{\prime}\). Suppose that we have a procedure LF-next\((w,k)\) which computes, given a word \(w\) and an integer \(k\), the pair \((s,q)\) where \(s\) is the largest integer such that \(w[k.k+s-1]\in L\) and \(q\) is the largest integer such that \(w[k+is.k+(i+1)s-1]=w[k.k+s-1]\), for \(i=1,\ldots,q-1\). The factorization of \(w\) can then be computed by iteratively calling LF-next starting from position 0. When a given call to LF-next returns, the factorization algorithm outputs the intervals \([k+is,k+(i+1)s-1]\), for \(i=0,\ldots,q-1\), and restarts the factorization at position \(k+qs\). [PERSON]'s algorithm implements LF-next using Lemma 3, which explains how to compute, given a word \(w\in P^{\prime}\) and a symbol \(a\in\Sigma\), whether \(wa\in P^{\prime}\), and thus makes it possible to compute the factorization using a left to right parsing. Note that, given a word \(w\in P^{\prime}\) with \(|\beta(w)|=i\), we have \(w[0..|w|-i-1]\in L\) and \(w=(w[0..|w|-i-1])^{q}w[0..r-1]\) with \(q=\lfloor\frac{|w|}{|w|-i}\rfloor\) and \(r=|w|\mod(|w|-i)\). For example, if \(w=abababab\), we have \(|w|=8\), \(|\beta(w)|=5\), \(q=2\), \(r=2\) and \(w=(abb)^{2}ab\). The code of [PERSON]'s algorithm is shown in Figure 1. The algorithm has \(O(|w|)\)-time and \(O(1)\)-space complexity. The following is an alternative formulation of [PERSON]'s algorithm by I et al. [8]:  
**Lemma 4**. : _Let \(j>0\) be any position of a string \(w\) such that \(w<w[i..|w|-1]\) for any \(0<i\leq j\) and \(lcp(w,w[j..|w|-1])\geq 1\). Then, \(w<w[k..|w|-1]\) also holds for any \(j<k\leq j+lcp(w,w[j..|w|-1])\)._  
**Lemma 5**. : _Let \(w\) be a string with \(CFL(w)=w_{1},w_{2},\ldots,w_{m}\). It holds that \(|w_{1}|=\min\{j\mid w[j..|w|-1]\)\(<w\}\) and \(w_{1}=w_{2}=\ldots=w_{q}=w[0..|w_{1}|-1]\), where \(q=1+\lfloor lcp(w,w[|w_{1}|..|w|-1])/\lfloor w_{1}\rfloor\)._  
Figure 1: [PERSON]’s algorithm to compute the Lyndon factorization of a string.