# Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings +
## 5 Computing the Lyndon Factorization of a Run-Length Encoded String
_If_ \(c_{j}=c_{i}\) _and_ \(l_{j}>l_{i}\)_, either_ \(c_{j}<c_{i+1}\) _and_ \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\
otin P^{\prime}\) _or_ \(c_{j}>c_{i+1}\)_,_ \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\in L^{\prime}\) _and_ \(1\) _holds for_ \(j+1\)_,_ \(\ell^{\prime}=0\)Proof. : The idea is the following: we apply Lemma 3 with the word \((uv)^{q}u\) as defined above and symbol \(c_{j}\). Observe that \(c_{j}\) is compared with symbol \(v[0]\), which is equal to \(c_{k+r-1}=c_{i-1}\) if \(z=1\) and to \(c_{k+r}=c_{i}\) otherwise. First note that, if \(z=1\), \(c_{j}\
eq c_{i-1}\), since otherwise we would have \(c_{j-1}=c_{i-1}=c_{j}\). In the first three cases, we obtain the first, second and third proposition of Lemma 3, respectively, for the word \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}c_{j}\). Independently of the derived proposition, it is easy to verify that the same proposition also holds for \(c_{k}^{l_{k}}\ldots c_{j-1}^{l_{j-1}}c_{j}^{m}\), \(m\leq l_{j}\). Consider now the fourth case. By a similar reasoning, we have that the third proposition of Lemma 3 holds for \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\). If we then apply Lemma 3 to \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\) and \(c_{j}\), \(c_{j}\) is compared to \(c_{i+1}\) and we must have \(c_{j}\
eq c_{i+1}\) as otherwise \(c_{i}=c_{j}=c_{i+1}\). Hence, either the first (if \(c_{j}<c_{i+1}\)) or the second (if \(c_{j}>c_{i+1}\)) proposition of Lemma 3 must hold for the word \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}+1}\). We prove by induction that invariant 1 is maintained. At the beginning, the variables \(j\) and \(\ell\) are initialized to \(k+1\) and \(0\), respectively, so the base case trivially holds. Suppose that the invariant holds for \(j,\ell\). Then, by Lemma 10, either \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\
otin P^{\prime}\) or it follows that the invariant also holds for \(j+1,\ell^{\prime}\), where \(\ell^{\prime}\) is equal to \(\ell+1\), if \(z=0\), \(c_{j}=c_{i}\) and \(l_{j}\leq l_{i}\), and to \(0\) otherwise. When \(c_{k}^{l_{k}}\ldots c_{j}^{l_{j}}\
otin P^{\prime}\) the algorithm returns the pair \((j-i,q)\), i.e., the length of \(uv\) and the corresponding exponent. The code of the algorithm is shown in Figure 3. We now prove that the algorithm runs in \(O(\rho)\) time. First, observe that, by definition of LR factorization, the for loop at line 4 is executed \(O(\rho)\) times. Suppose that the number of iterations of the while loop at line 2 is \(n\) and let \(k_{1},k_{2},\ldots,k_{n+1}\) be the corresponding values of \(k\), with \(k_{1}=0\) and \(k_{n+1}=|R|\). We now show that the \(s\)-th call to LF-rle-next performs less than \(2(k_{s+1}-k_{s})\) iterations, which will yield \(O(\rho)\) number of iterations in total. This analysis is analogous to the one used by [PERSON]. Suppose that \(i^{\prime}\), \(j^{\prime}\) and \(z^{\prime}\) are the values of \(i\), \(j\) and \(z\) at the end of the \(s\)-th call to LF-rle-next. The number of iterations performed during this call is equal to \(j^{\prime}-k_{s}\). We have \(k_{s+1}=k_{s}+q(j^{\prime}-i^{\prime})\), where \(q=\lfloor\frac{\frac{\rho}{r}-k_{s}-z}{j-i^{\prime}}\rfloor\), which implies \(j^{\prime}-k_{s}<2(k_{s+1}-k_{s})+1\), since, for any positive integers \(x,y,\)\(x<2\lfloor x/y\rfloor y\) holds.