BDBComp
Parceria:
SBC
A Modification of the Landau-Vishkin Algorithm Computing Longest Common Extensions via Suffix Arrays

Rodrigo de Castro MirandaMaurício Ayala-Rincón

Landau and Vishkin developed an O(kn) algorithm for the approximate string matching problem, where k is the maximum number of admissible errors and n the length of the text. This algorithm uses suffix trees for an O(1) running time computation of the longest common extensions between strings. We present a variation of this algorithm which uses suffix arrays for computing the longest common extensions.

http://www.lbd.dcc.ufmg.br/colecoes/bsb/2005/030.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD