Permuted longest-common-prefix array

Juha Kärkkäinen, Giovanni Manzini, Simon J. Puglisi

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

Abstract

The longest-common-prefix (LCP) array is an adjunct to the suffix array that allows many string processing problems to be solved in optimal time and space. Its construction is a bottleneck in practice, taking almost as long as suffix array construction. In this paper, we describe algorithms for constructing the permuted LCP (PLCP) array in which the values appear in position order rather than lexicographical order. Using the PLCP array, we can either construct or simulate the LCP array. We obtain a family of algorithms including the fastest known LCP construction algorithm and some extremely space efficient algorithms. We also prove a new combinatorial property of the LCP values.

Lingua originaleInglese
Titolo della pubblicazione ospiteCombinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings
Pagine181-192
Numero di pagine12
DOI
Stato di pubblicazionePubblicato - 2009
Pubblicato esternamente
Evento20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009 - Lille, France
Durata: 22 giu 200924 giu 2009

Serie di pubblicazioni

NomeLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5577 LNCS
ISSN (stampa)0302-9743
ISSN (elettronico)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009
Paese/TerritorioFrance
CittàLille
Periodo22/06/0924/06/09

Fingerprint

Entra nei temi di ricerca di 'Permuted longest-common-prefix array'. Insieme formano una fingerprint unica.

Cita questo