| Autor: |
Bonizzoni, Paola, De Felice, Clelia, Zaccagnino, Rocco, Zizza, Rosalba |
| Rok vydání: |
2017 |
| Předmět: |
|
| Zdroj: |
Advances in Applied Mathematics, Vol. 101, pp. 281-319, 2018 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1016/j.aam.2018.08.005 |
| Popis: |
Motivated by applications to string processing, we introduce variants of the Lyndon factorization called inverse Lyndon factorizations. Their factors, named inverse Lyndon words, are in a class that strictly contains anti-Lyndon words, that is Lyndon words with respect to the inverse lexicographic order. The Lyndon factorization of a nonempty word w is unique but w may have several inverse Lyndon factorizations. We prove that any nonempty word w admits a canonical inverse Lyndon factorization, named ICFL(w), that maintains the main properties of the Lyndon factorization of w: it can be computed in linear time, it is uniquely determined, it preserves a compatibility property for sorting suffixes. In particular, the compatibility property of ICFL(w) is a consequence of another result: any factor in ICFL(w) is a concatenation of consecutive factors of the Lyndon factorization of w with respect to the inverse lexicographic order. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
