The main goal of this paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15] that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we propose sorts the suffixes by starting from the leftmost Lyndon factors, even if the whole text or the complete Lyndon factorization are not yet available.
Mantaci, S., Restivo, A., Rosone, G., Sciortino, M. (2014). Suffix array and Lyndon factorization of a text. JOURNAL OF DISCRETE ALGORITHMS, 28, 2-8 [10.1016/j.jda.2014.06.001].
Suffix array and Lyndon factorization of a text
MANTACI, Sabrina;RESTIVO, Antonio;SCIORTINO, Marinella
2014-01-01
Abstract
The main goal of this paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15] that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we propose sorts the suffixes by starting from the leftmost Lyndon factors, even if the whole text or the complete Lyndon factorization are not yet available.File | Dimensione | Formato | |
---|---|---|---|
[18]_MRRS_JDA2014.pdf
Solo gestori archvio
Descrizione: Articolo su rivista principale
Dimensione
285.36 kB
Formato
Adobe PDF
|
285.36 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.