@inproceedings{1249f2128a0a41418ab28b0ccf2e3dab,
title = "Faster external memory LCP array construction",
abstract = "The suffix array, perhaps the most important data structure in modern string processing, needs to be augmented with the longest-common-prefix (LCP) array in many applications. Their construction is often a major bottleneck especially when the data is too big for internal memory. We describe two new algorithms for computing the LCP array from the suffix array in external memory. Experiments demonstrate that the new algorithms are about a factor of two faster than the fastest previous algorithm.",
keywords = "External memory algorithms, LCP array, Suffix array",
author = "Juha K{\"a}rkk{\"a}inen and Dominik Kempa",
note = "Publisher Copyright: {\textcopyright} Juha K{\"a}rkk{\"a}inen and Dominik Kempa.; 24th Annual European Symposium on Algorithms, ESA 2016 ; Conference date: 22-08-2016 Through 24-08-2016",
year = "2016",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.ESA.2016.61",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christos Zaroliagis and Piotr Sankowski",
booktitle = "24th Annual European Symposium on Algorithms, ESA 2016",
}