A Scalable and Efficient Systolic Algorithm for the Longest Common Subsequence Problem.
Yen‐Chun Lin, Jih-Wei Yeh · 2002
this paper, a scalable and efficient systolic algorithm is presented. For two given strings of length m and n,wherem # 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