Inducing the Lyndon Array

Sabrina Mantaci, Marinella Sciortino, Felipe A. Louza, Felipe A. Louza, Guilherme P. Telles, Giovanni Manzini

Risultato della ricerca: Conference contribution

6 Citazioni (Scopus)

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.
Lingua originaleEnglish
Titolo della pubblicazione ospiteString Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings
Pagine138-151
Numero di pagine14
Stato di pubblicazionePublished - 2019

Serie di pubblicazioni

NomeLECTURE NOTES IN COMPUTER SCIENCE

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • ???subjectarea.asjc.1700.1700???

Fingerprint Entra nei temi di ricerca di 'Inducing the Lyndon Array'. Insieme formano una fingerprint unica.

Cita questo