2026-07-21T21:02:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6402 2024-03-06T10:38:11Z ddc:004 open_access

Faster External Memory LCP Array Construction Kärkkäinen, Juha Kempa, Dominik LCP array suffix array external memory algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juha Kärkkäinen and Dominik Kempa 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.61 urn:nbn:de:0030-drops-64026 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.61 eng https://creativecommons.org/licenses/by/3.0/legalcode