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

TY - JOUR

T1 - Recovering an LCS in O(n2/w) time and space

AU - Iliopoulos, Costas S.

AU - Pinzon, Yoan J.

PY - 2002/6

Y1 - 2002/6

N2 - Here we make use of word-level parallelism to recover a longest common subsequence of two input strings both of length n in 0(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 strings is close to w its complexity is reduced to linear time and space.

AB - Here we make use of word-level parallelism to recover a longest common subsequence of two input strings both of length n in 0(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 strings is close to w its complexity is reduced to linear time and space.

M3 - Article

VL - 3

SP - 41

EP - 51

JO - Colombian Journal of Computation

JF - Colombian Journal of Computation

IS - 1

M1 - N/A

ER -