In this paper we propose a variant of the induced suffix sorting algorithm by Nong (TOIS, 2013) that computes simultaneously the Lyndon array and the suffix array of a text in O(n) time using O(n) words of working space, where n is the length of the text and is the alphabet size. Our result improves the previous best space requirement for linear time computation of the Lyndon array. In fact, all the known linear algorithms for Lyndon array computation use suffix sorting as a preprocessing step and use O(n) words of working space in addition to the Lyndon array and suffix array. Experimental results with real and synthetic datasets show that our algorithm is not only space-efficient but also fast in practice.

Louza F.A., Mantaci S., Manzini G., Sciortino M., Telles G.P. (2019). Inducing the Lyndon Array. In N.R. Brisaboa, S.J. Puglisi (a cura di), String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings (pp. 138-151). Springer [10.1007/978-3-030-32686-9_10].

Inducing the Lyndon Array

Mantaci S.
;
Sciortino M.
;
2019

Abstract

In this paper we propose a variant of the induced suffix sorting algorithm by Nong (TOIS, 2013) that computes simultaneously the Lyndon array and the suffix array of a text in O(n) time using O(n) words of working space, where n is the length of the text and is the alphabet size. Our result improves the previous best space requirement for linear time computation of the Lyndon array. In fact, all the known linear algorithms for Lyndon array computation use suffix sorting as a preprocessing step and use O(n) words of working space in addition to the Lyndon array and suffix array. Experimental results with real and synthetic datasets show that our algorithm is not only space-efficient but also fast in practice.
Settore INF/01 - Informatica
Settore ING-INF/05 - Sistemi Di Elaborazione Delle Informazioni
978-3-030-32685-2
978-3-030-32686-9
https://link.springer.com/chapter/10.1007/978-3-030-32686-9_10
Louza F.A., Mantaci S., Manzini G., Sciortino M., Telles G.P. (2019). Inducing the Lyndon Array. In N.R. Brisaboa, S.J. Puglisi (a cura di), String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings (pp. 138-151). Springer [10.1007/978-3-030-32686-9_10].
File in questo prodotto:
File Dimensione Formato  
camera-ready.pdf

accesso aperto

Tipologia: Post-print
Dimensione 492.94 kB
Formato Adobe PDF
492.94 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10447/396233
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact