Another efficient systolic algorithm for the longest common subsequence problem

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. In this paper, a fast systolic algorithm for the LCS problem is presented. For two strings of length In and n, where m greater than or equal to n, the problem can be solved in m+2n-1 time steps. The algorithm achieves the tight lower bound of the computation steps when symbols are input sequentially to a linear array of n processors. The algorithm is faster than the other systolic algorithm that also achieves the tight lower bound. The systolic algorithm can be modified to take only m+n steps on a multicomputer by using the broadcast operation.