Efficient parallel string comparison

The longest common subsequence (LCS) problem is a classical method of string comparison. Several coarse-grained parallel algorithms for the LCS problem have been proposed in the past. However. none of these algorithms achieve scalable communication. In this paper. we propose the first coarse-grained parallel LCS algorithm with scalable communication. Moreover, the algorithm is work-optimal, synchronisation-efficient, and solves a more general problem of semi-local string comparison, improving in at least two of these aspects on each of the predecessors