Parallel computation of Longest-Common-Subsequence Conference Paper uri icon

abstract

  • A parallel algorithm for finding the longest common subsequence of two strings is presented. Our algorithm is executed on r processors, with r equal to the total number of pairs of positions at which two symbols match. Given two strings of length m and n respectively, m <- n, with preprocessing allowed, our algorithm achieves O(loglog2n) time complexity where is the longest common subsequence. Fast computing of Longest-Common-Subsequence is made possible due to the exploiting of the parallelism.

name of conference

  • Advances in Computing and Information ICCI '90

author list (cited authors)

  • Lu, M.

complete list of authors

  • Lu, M

editor list (cited editors)

  • Akl, S. G., Fiala, F., & Koczkodaj, W. W.

publication date

  • 1990