An Efficient Systolic Algorithm for the Longest Common Subsequence Problem

被引：0
作者：
Yen-Chun Lin
Jyh-Chian Chen
机构：
[1] National Taiwan University of Science and Technology,Dept. of Electronic Engineering
[2] Lunghwa Junior College of Technology and Commerce,Dept. of Electronic Engineering
[3] Taoyuan,undefined
[4] Taiwan,undefined
[5] Dept. of Electronic Engineering and National Taiwan University of Science and Technology,undefined
来源：
The Journal of Supercomputing | 1998年 / 12卷
关键词：
Longest common subsequence; multicomputer; parallel algorithm; systolic array; VLSI;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A longest common subsequence (LCS) of two strings is a common subsequence of the two strings of maximal length. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). In this paper, a fast linear systolic algorithm that improves on previous systolic algorithms for solving the LCS problem is presented. For two given strings of length m and n, where m ≥ n, the LLCS and an LCS can be found in m + 2n − 1 time steps. This algorithm achieves the tight lower bound of the time complexity under the situation where symbols are input sequentially to a linear array of n processors. The systolic algorithm can be modified to take only m + n steps on multicomputers by using the scatter operation.
引用
收藏
页码：373 / 385
页数：12
相关论文
共 43 条
[1]  
Agerwala T.(1995)SP2 system architecture IBM Systems Journal 34 152-184
[2]  
Martin J. L.(1976)Bounds on the complexity of the longest common subsequence problem Journal of the Association for Computing Machinery 23 1-12
[3]  
Mirza J. H.(1986)Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings Information Processing Letters 23 63-69
[4]  
Sadler D. C.(1990)Efficient parallel algorithms for string editing and related problems SIAM Journal on Computing 19 968-988
[5]  
Dias D. M.(1992)Fast linear-space computations of longest common subsequences Theoretical Computer Science 92 3-17
[6]  
Snir M.(1987)The longest common subsequence problem revisited Algorithmica 2 315-336
[7]  
Aho A.(1992)Spatial machines: A more realistic approach to parallel computation Communications of the ACM 35 61-73
[8]  
Hirschberg D.(1975)A linear space algorithm for computing maximal common subsequences Communications of the ACM 18 341-343
[9]  
Ullman J.(1977)Algorithms for the longest common subsequence problem Journal of the ACM 24 664-675
[10]  
Apostolico A.(1987)A linear-space algorithm for the LCS problem Acta Informatica 24 353-362
12345