Thumbnail
Access Restriction
Subscribed

Author Krkkinen, Juha ♦ Kempa, Dominik
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword External memory algorithms ♦ LCP array ♦ Suffix array
Abstract One of the most important data structures for string processing—the suffix array—needs to be augmented with the longest-common-prefix (LCP) array in numerous applications. We describe the first external memory algorithm for constructing the LCP array given the suffix array as input. The only previous way to compute the LCP array for data that is bigger than the RAM is to use an external memory suffix array construction algorithm (SACA) with complex modifications to produce the LCP array as a by-product. Compared to the best prior method, our algorithm needs much less disk space (by more than a factor of three) and is significantly faster. Furthermore, our algorithm can be combined with any SACA, including a better one developed in the future.
Description Author Affiliation: Helsinki Institute of Information Technology and Department of Computer Science, University of Helsinki, Finland (Krkkinen, Juha; Kempa, Dominik)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-04-05
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 22
Starting Page 1
Ending Page 22


Open content in new tab

   Open content in new tab
Source: ACM Digital Library