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 -