Permuted longest-common-prefix array

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

doi:10.1007/978-3-642-02441-2_17

Permuted longest-common-prefix array

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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.

Original language	English
Title of host publication	Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings
Pages	181-192
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-02441-2_17
Publication status	Published - 2009
Externally published	Yes
Event	20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009 - Lille, France Duration: 22 Jun 2009 → 24 Jun 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5577 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009
Country/Territory	France
City	Lille
Period	22/06/09 → 24/06/09

Access to Document

10.1007/978-3-642-02441-2_17

Cite this

Kärkkäinen, J., Manzini, G., & Puglisi, S. J. (2009). Permuted longest-common-prefix array. In Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings (pp. 181-192). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5577 LNCS). https://doi.org/10.1007/978-3-642-02441-2_17

@inproceedings{6fb9aef6a45b434591e8a704f532b035,

title = "Permuted longest-common-prefix array",

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.",

author = "Juha K{\"a}rkk{\"a}inen and Giovanni Manzini and Puglisi, {Simon J.}",

note = "Funding Information: This work is supported by the Academy of Finland grant 118653 (ALGODAN), by the Italy-Israel Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”, and by the Australian Research Council.; 20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009 ; Conference date: 22-06-2009 Through 24-06-2009",

year = "2009",

doi = "10.1007/978-3-642-02441-2_17",

language = "English",

isbn = "3642024408",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "181--192",

booktitle = "Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings",

}

Kärkkäinen, J, Manzini, G & Puglisi, SJ 2009, Permuted longest-common-prefix array. in Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5577 LNCS, pp. 181-192, 20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009, Lille, France, 22/06/09. https://doi.org/10.1007/978-3-642-02441-2_17

Permuted longest-common-prefix array. / Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J.
Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings. 2009. p. 181-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5577 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Permuted longest-common-prefix array

AU - Kärkkäinen, Juha

AU - Manzini, Giovanni

AU - Puglisi, Simon J.

N1 - Funding Information: This work is supported by the Academy of Finland grant 118653 (ALGODAN), by the Italy-Israel Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”, and by the Australian Research Council.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70350648554&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02441-2_17

DO - 10.1007/978-3-642-02441-2_17

M3 - Conference contribution

AN - SCOPUS:70350648554

SN - 3642024408

SN - 9783642024405

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 181

EP - 192

BT - Combinatorial Pattern Matching - 20th Annual Symposium, CPM 2009, Proceedings

T2 - 20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009

Y2 - 22 June 2009 through 24 June 2009

ER -

Permuted longest-common-prefix array

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this