Parallel computation of Longest-Common-Subsequence
- Additional Document Info
- View All
Springer-Verlag Berlin Heidelberg 1990. 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.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
author list (cited authors)
complete list of authors