Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications

By Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, Kunsoo Park. Annual Symposium on Combinatorial Pattern Matching, 2001

526 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Linear work suffix array construction (2006, methodology): “There are simple linear time algorithms for computing the lcp array from the suffix array [Kasai et al. 2001; Manzini 2004], but they do not appear to be suitable for parallel or external computation.”
A taxonomy of suffix array construction algorithms (2007, background): “Since lcp can be computed in linear time from SAx [Kasai et al. 2001; Manzini 2004], also as a byproduct of some of the SACAs discussed below, we do not consider its construction further in this article.”
Replacing suffix trees with enhanced suffix arrays (2004, methodology): “[20] presented a linear time algorithm to simulate the bottom-up traversal of a suffix tree with a suffix array and its lcp-information.”
Compressed Suffix Trees with Full Functionality (2007, methodology): “[17] showed that a bottom-up traversal of a suffix tree can be simulated by using only the suffix array and an array storing a set of the lengths of the longest”
Simple Linear Work Suffix Array Construction (2003, methodology): “There is a linear time algorithm for computing the lcp array from the suffix array [ 27 ], but it does not appear to be suitable for parallel or external computation.”