Recovering an LCS in O(n^2/w) time and space

  • Costas S. Iliopoulos Departament of Computer Science, King's College London, Strand, London, WC2R 2LS, England,
  • Yoan Pinzón Ardila Laboratorio de Cómputo Especializado, Universidad Autónoma de Bucaramanga, Calle 48 No 39-234, Bucaramanga, Colombia
Resumen Cómo citar Descargas

Resumen

Here we make use of word-level parallelism to recover a longest common subsequence of two input strings both of length n in O(n2/w)  time and space, where w is the number of bits in a machine word. For the special case where one of the input atrings is close to w its complexity is reduced to linear time and space.

Keywords: Longest Common Subsequence, Bit-parallelism.

Cómo citar
Iliopoulos, C. S., & Pinzón Ardila, Y. (2002). Recovering an LCS in O(n^2/w) time and space. Revista Colombiana De Computación, 3(1), 41–51. Recuperado a partir de https://revistas.unab.edu.co/index.php/rcc/article/view/1107

Descargas

Los datos de descargas todavía no están disponibles.
Publicado
2002-06-01
Número
Vol. 3 Núm. 1 (2002): Revista Colombiana de Computación (Enero-Junio)
Sección
Artículo de investigación científica y tecnológica

Métricas

QR Code