Another efficient systolic algorithm for the longest common subsequence problem

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. In this paper, a fast systolic algorithm for the LCS problem is presented. For two strings of length m and n, where m≥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.

Key words:

• longest common subsequence
• multicomputer
• parallel algorithm
• systolic array

Notes

Correspondence addressee