License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.61
URN: urn:nbn:de:0030-drops-64026
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6402/
Go to the corresponding LIPIcs Volume Portal

Kärkkäinen, Juha ; Kempa, Dominik

Faster External Memory LCP Array Construction

pdf-format:
LIPIcs-ESA-2016-61.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{krkkinen_et_al:LIPIcs:2016:6402,
  author =	{Juha K{\"a}rkk{\"a}inen and Dominik Kempa},
  title =	{{Faster External Memory LCP Array Construction}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6402},
  URN =		{urn:nbn:de:0030-drops-64026},
  doi =		{10.4230/LIPIcs.ESA.2016.61},
  annote =	{Keywords: LCP array, suffix array, external memory algorithms}
}

Keywords: LCP array, suffix array, external memory algorithms
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI