文章基本信息

标题：Faster External Memory LCP Array Construction
本地全文：下载
作者：Juha K{\"a}rkk{\"a}inen ; Dominik Kempa
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：57
页码：61:1-61:16
DOI：10.4230/LIPIcs.ESA.2016.61
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：LCP array; suffix array; external memory algorithms