Portal de Periódicos da CAPES

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

2001; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-48194-x_17

1611-3349

Toru Kasai, Gun-Ho Lee, Hiroki Arimura, Setsuo Arikawa, Kunsoo Park,

Genomics and Phylogenetic Studies

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 sim- ulate the bottom-up traversal of a suffix tree with a suffix array combined with the longest common prefix information.