Revista Colombiana de Computación (Jun 2002)

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

  • Costas S. Iliopoulos,
  • Yoan Pinzón Ardila

Journal volume & issue
Vol. 3, no. 1

Abstract

Read online

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.