An efficient linear systolic algorithm for recovering longest common subsequences

This paper presents an implementable linear systolic array of m cells which computes both a longest common subsequence and its length in time n+3m+p-1, where m⩽n and p is the length of the LCS. Our algorithm can be extended to recover more than one LCS. Another important property of our algorithm is that each element of an LCS is extracted with its ranks in A and B respectively. Thus we can precisely localize the elements of A and B which match each other. In practice, this information is essential in some situations