# Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings +
## 5 Computing the Lyndon Factorization of a Run-Length Encoded String  
In this section we present an algorithm to compute the Lyndon factorization of a string given in RLE form. The algorithm is based on [PERSON]'s original algorithm and on a combinatorial property between the Lyndon factorization of a string and its RLE, and has \(O(\rho)\)-time and \(O(1)\)-space complexity, where \(\rho\) is the length of the RLE. We start with the following Lemma:  
**Lemma 9**. : _Let \(w\) be a word over \(\Sigma\) and let \(w_{1},w_{2},\ldots,w_{m}\) be its Lyndon factorization. For any \(1\leq i  
Based on Lemma 1, the factorization of \(R\) can then be computed by iteratively calling LF-rle-next starting from position 0. When a given call to LF-rle-next returns, the factorization algorithm outputs the intervals \([k+is,k+(i+1)s-1]\) in \(R\), for \(i=0,\ldots,q-1\), and restarts the factorization at position \(k+qs\). We now present the LF-rle-next algorithm. Analogously to [PERSON]'s algorithm, it reads the RLE sequence from left to right maintaining two integers, \(j\) and \(\ell\), which satisfy the following invariant:  
\[c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}\in P^{\prime}; \tag{1}\] \[\ell= \begin{cases}|\texttt{rle}(\beta(c_{k}^{l_{k}}\ldots c_{j-1} ^{l_{j-1}}))|&\text{ if }j-k>1,\\ 0&\text{ otherwise.}\end{cases} \]  
The integer \(j\), initialized to \(k+1\), is the index of the next run to read and is incremented at each iteration until either \(j=|R|\) or \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}\in P^{\prime}\). The integer \(\ell\), initialized to 0, is the length in runs of the longest border of \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}\), if \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}\) spans at least two runs, and equal to 0 otherwise. For example, in the case of the word \(ab^{2}ab^{2}ab\) we have \(\beta(ab^{2}ab^{2}ab)=ab^{2}ab\) and \(\ell=4\). Let \(i=k+\ell\). In general, if \(\ell>0\), we have  
\[l_{j-1}\leq l_{i-1},l_{k}\leq l_{j-\ell}, \tag{2}\] \[\beta(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}})=c_{k}^{l_{k}}c_{k+1} ^{l_{k+1}}\ldots c_{i-2}^{l_{j-2}}c_{i-1}^{l_{j-1}}=c_{j-\ell}^{l_{k}}c_{j- \ell+1}^{l_{j-\ell+1}}\ldots c_{j-2}^{l_{j-2}}c_{j-1}^{l_{j-1}}.\]  
Note that the longest border may not fully cover the last (first) run of the corresponding prefix (suffix). Such the case is for example for the word \(ab^{2}a^{2}b\). However, since \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}\in P^{\prime}\) it must hold that \(l_{j-\ell}=l_{k}\), i.e., the first run of the suffix is fully covered. Let  
\[z= \begin{cases}1&\text{ if }\ell>0\wedge l_{j-1}<l_{i-1},\\ 0&\text{ otherwise.}\end{cases} \]  
Informally, the integer \(z\) is equal to 1 if the longest border of \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}\) does not fully cover the run \((c_{i-1},l_{i-1})\). By \(1\) we have that \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}\) can be written as \((uv)^{q}u\), where  
\[q=\lfloor\frac{i-k-z}{l-l}\rfloor,r=z+(j-k-z)\mod(j-i), \tag{3}\] \[u=c_{j-r}^{l_{j-r}}\ldots c_{j-1}^{l_{j-1}},uv=c_{k}^{l_{k}} \ldots c_{j-\ell-1}^{l_{j-\ell-1}}=c_{i-r}^{l_{j-r}}\ldots c_{j-r-1}^{l_{j-r-1 }},\] \[uv\in\ L^{\prime}\]  
For example, in the case of the word \(ab^{2}ab^{2}ab\), for \(k=0\), we have \(j=6,i=4,q=2,r=2\). The algorithm is based on the following Lemma:  
**Lemma 10**. : _Let \(j,\ell\) be such that invariant 1 holds and let \(s=i-z\). Then, we have the following cases:_  
1. _If_ \(c_{j}<c_{s}\) _then_ \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\
otin P^{\prime}\)_;_
2. _If_ \(c_{j}>c_{s}\) _then_ \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\in L^{\prime}\) _and_ 1 _holds for_ \(j+1\)_,_ \(\ell^{\prime}=0\)_;_  
_Moreover, if \(z=0\), we also have:_  
1. _If_ \(c_{j}=c_{i}\) _and_ \(l_{j}\leq l_{i}\)_, then_ \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\in P^{\prime}\) _and_ 1 _holds for_ \(j+1\)_,_ \(\ell^{\prime}=\ell+1\)_;_
2.