×

zbMATH — the first resource for mathematics

Linear-time longest-common-prefix computation in suffix arrays and its applications. (English) Zbl 0990.68639
Amir, Amihood (ed.) et al., Combinatorial pattern matching. 12th annual symposium, CPM 2001, Jerusalem, Israel, July 1-4, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2089, 181-192 (2001).
Summary: We present a linear-time algorithm to compute the longest common prefix information in suffix arrays. As two applications of our algorithm, we show that our algorithm is crucial to the effective use of block-sorting compression, and we present a linear-time algorithm to simulate the bottom-up traversal of a suffix tree with a suffix array combined with the longest common prefix information.
For the entire collection see [Zbl 0968.00055].

MSC:
68W05 Nonnumerical algorithms
68P10 Searching and sorting
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: Link