Recovering an LCS in O(n^2/w) time and space
Abstract
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.
How to Cite
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. Retrieved from https://revistas.unab.edu.co/rcc/article/view/1107
Downloads
Download data is not yet available.
Published
2002-06-01
Section
Article of scientific and technological research
| Article metrics | |
|---|---|
| Abstract views | |
| Galley views | |
| PDF Views | |
| HTML views | |
| Other views | |
Altmetric
Scan to share
