# Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings +
## 4 Improved Algorithm for Small Alphabets  
Let \(w\) be a word over an alphabet \(\Sigma\) with \(CFL(w)=w_{1},w_{2},\ldots,w_{m}\) and let \(\tilde{c}\) be the smallest symbol in \(\Sigma\). Suppose that there exists \(k\geq 2,i\geq 1\) such that \(\tilde{c}^{k}\) is a prefix of \(w_{i}\). If the last symbol of \(w\) is not \(\tilde{c}\), then by Theorem 1 and by the properties of Lyndon words, \(\tilde{c}^{k}\) is a prefix of each of \(w_{i+1},w_{i+2},\ldots,w_{m}\). This property can be exploited to devise an algorithm for Lyndon factorization that can potentially skip symbols. Note that we assume Property 1, i.e., the output of the algorithm is the sequence of _intervals_ of the factors in \(CFL(w)\), as otherwise we have to read all the symbols of \(w\) to output \(CFL(w)\). Our algorithm is based on the alternative formulation of [PERSON]'s algorithm by I et al. [8]. Given a set of strings \(\mathcal{P}\), let \(Occ_{\mathcal{P}}(w)\) be the set of all (starting) positions in \(w\) corresponding to occurrences of the strings in \(\mathcal{P}\). We start with the following Lemmas:  
**Lemma 6**. : _Let \(w\) be a word and let \(s=\max\{i\mid w[i]>\tilde{c}\}\cup\{-1\}\). Then, we have \(CFL(w)=CFL(w[0..s])CFL(\tilde{c}^{(|w|-1-s)})\)._  
Proof. : If \(s=-1\) or \(s=|w|-1\) the Lemma plainly holds. Otherwise, Let \(w_{i}\) be the factor in \(CFL(w)\) such that \(s\) belongs to \([a_{i},b_{i}]\), the interval of \(w_{i}\). To prove the claim we have to show that \(b_{i}=s\). Suppose by contradiction that \(s<b_{i}\), which implies \(|w_{i}|\geq 2\). Then, \(w_{i}[|w_{i}|-1]=\tilde{c}\), which contradicts the second property of Lyndon words. For example, if \(w=ababababbababa\), we have \(CFL(w)=CFL(abababaabbaab)\)\(CFL(aa)\). **Lemma 7**. : _Let \(w\) be a word such that \(\tilde{c}\tilde{c}\) occurs in it and let \(s=\min Occ_{\{\tilde{c}\tilde{c}\}}(w)\). Then, we have \(CFL(w)=CFL(w[0..s-1])CFL(w[s..|w|-1])\)._  
Proof. : Let \(w_{i}\) be the factor in \(CFL(w)\) such that \(s\) belongs to \([a_{i},b_{i}]\), the interval of \(w_{i}\). To prove the claim we have to show that \(a_{i}=s\). Suppose by contradiction that \(s>a_{i}\), which implies \(|w_{i}|\geq 2\). If \(s=b_{i}\) then \(w_{i}[|w_{i}|-1]=\tilde{c}\), which contradicts the second property of Lyndon words. Otherwise, since \(w_{i}\) is a Lyndon word it must hold that \(w_{i}<\textsc{rot}(w_{i},s-a_{i})\). This implies at least that \(w_{i}[0]=w_{i}[1]=\tilde{c}\), which contradicts the hypothesis that \(s\) is the smallest element in \(Occ_{\{\tilde{c}\tilde{c}\}}(w)\). For example, if \(w=abaabaabaaba\), we have \(CFL(w)=CFL(ab)\)\(CFL(aabaabaaba)\). **Lemma 8**. : _Let \(w\) be a word such that \(w[0]=w[1]=\tilde{c}\) and \(w[|w|-1]\
eq\tilde{c}\). Let \(r\) be the smallest position in \(w\) such that \(w[r]\
eq\tilde{c}\). Let also \(\mathcal{P}=\{\tilde{c}^{\prime}c\mid c\leq w[r]\}\). Then we have_  
\[b_{1}=\min\{s\in Occ_{\mathcal{P}}(w)\mid w[s..|w|-1]<w\}\cup\{|w|\}-1\,,\]  
_where \(b_{1}\)  
For example, if \(w=aabaabaab\), we have \(\mathcal{P}=\{aaa,aab\}\), \(Occ_{\mathcal{P}}(w)=\{0,3,7\}\) and \(b_{1}=6\). Based on these Lemmas, we can devise a faster factorization algorithm for words containing runs of \(\tilde{c}\). The key idea is that, using Lemma 8, it is possible to skip symbols in the computation of \(b_{1}\), if a suitable string matching algorithm is used to compute \(Occ_{\mathcal{P}}(w)\). W.l.o.g. we assume that the last symbol of \(w\) is different from \(\tilde{c}\). In the general case, by Lemma 6, we can reduce the factorization of \(w\) to the one of its longest prefix with last symbol different from \(\tilde{c}\), as the remaining suffix is a concatenation of \(\tilde{c}\) symbols, whose factorization is a sequence of factors equal to \(\tilde{c}\). Suppose that \(\tilde{c}\tilde{c}\) occurs in \(w\). By Lemma 7 we can split the factorization of \(w\) in \(CFL(u)\) and \(CFL(v)\) where \(uv=w\) and \(|u|=\min Occ_{\{\tilde{c}\}}(w)\). The factorization of \(CFL(u)\) can be computed using [PERSON]'s original algorithm.