Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Information Science and Engineering, Vol.18 No.4, pp.507-518 (July 2002)


A Scalable and Efficient Systolic Algorithm for the Longest
Common Subsequence Problem*

Yen-Chun Lin and Jih-Wei Yeh+
Department of Computer Science and Information Engineering
+Department of Electronic Engineering
Naitonal Taiwan University of Science and Technology
Taipei, 106 Taiwan
E-mail: yclin@computer.org

A longest common subsequence (LCS) of two strings is a common subsequence of two strings of maximal length. The LCS problem is that of finding an LCS of two given strings and the length of the LCS. This problem has been the subject of much research because its solution can be applied in many areas. In this paper, a scalable and efficient systolic algorithm is presented. For two given strings of length m and n, where m ? n, the algorithm can solve the LCS problem in m + 2r - 1 (respectively n + 2r - 1) time steps with r < n/2 (respectively r < m/2) processors. Experimental results show that the algorithm can be faster on multicomputers than all the previous systolic algorithms for the same problem.

Keywords: longest common subsequence, multicomputers, parallel algorithms, scalable algorithms, systolic arrays

Full Text () Retrieve PDF document (200207_04.pdf)

Received August 27, 2001; accepted April 15, 2002.
Communicated by Jang-Ping Sheu, Myongsoon Park and Makoto Takizawa.
* A preliminary version of this paper was presented at the 2000 International Computer Symposium, Workshop on Algorihtms and Theory of Computation, Dec. 6-8, 2000, Chiayi, Taiwan.