PARALLEL ALGORITHMS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM
Academic Article

Overview

Research

Identity

Additional Document Info

View All

Overview

abstract

A subsequence of a given string is any string obtained by deleting none or some symbols from the given string. A longest common subsequence of two strings is a common subsequence of both that is as long as any other common subse-quences. The longest common subsequence problem is to find the longest common subsequence of two given strings. The bound on the complexity of this problem under the decision tree model is known as mn if the number of distinct symbols that can appear in strings is infinite, where m and n are the lengths of the two strings, respectively, and m < n. In this paper, we propose two parallel algorithms for this problem on the CREW-PRAM model. One takes 0(log2rn + log n) time with mn/ log m processors, which is faster than all the existing algorithms on the same model. The other takes O(log2m log log m) time with mn/log2 m log log m processors when log2 m log log m > logn, or otherwise O(logn) time with mn/ log n processors, which is optimal in the sense that the time x processors bound matches the complexity bound of the problem. Both algorithms exploit nice properties of the LCS problem that are discovered in this paper. 1994 IEEE