An Efficient Systolic Algorithm for the Longest Common Subsequence Problem |
| |
| Authors: | Lin Yen-Chun Chen Jyh-Chian |
| |
| Affiliation: | (1) Dept. of Electronic Engineering, National Taiwan University of Science and Technology, P.O. Box 90-100, Taipei, 106, Taiwan;(2) Dept. of Electronic Engineering, Lunghwa Junior College of Technology and Commerce, Taoyuan, Taiwan, Dept. of Electronic Engineering and National Taiwan University of Science and Technology, P.O. Box 90-100, Taipei, 106, Taiwan |
| |
| Abstract: | 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. |
| |
| Keywords: | Longest common subsequence multicomputer parallel algorithm systolic array VLSI |
| 本文献已被 SpringerLink 等数据库收录！ |
|
